Ruudukko

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 2525;

string board[N][N];

unordered_map<int, string> m;

int isFirst(string a, string b) {
	
	int n = a.length();
	for(int i = 0; i < n; ++i) {
		int x = (int) a[i];
		int y = (int) b[i];
		if(x < y) {
			return 1;
		}
		if(x > y) {
			return 2;
		}
	}
	return 1;
}


int main() {
	int n;
	cin >> n;
	for(int y = 1; y <= n; ++y) {
		string s;
		cin >> s;
		for(int x = 0; x < n; ++x) {
			board[y][x+1] = s[x];
		}
	}	


	string s = "";
	s += board[1][1];
	m[1] = s;


	for(int sum = 3; sum <= 2*n; ++sum) {
		for(int y = 1; y < sum; ++y) {
			int x = sum - y;
			if(y > n || x > n) continue;
			if(y == 1) {
				m[x] = m[x-1] + board[1][x];
				continue;
			}
			if(x == 1) {
				m[n*(y-1) + 1] = m[n*(y-2) + 1] + board[y][1];
				continue;
			}

			string a = m[n*(y-1) + x - 1];
			string b = m[n*(y-2) + x];
			if(isFirst(a, b) == 1) {
				m[n*(y-1) + x] = a + board[y][x];
			} else {
				m[n*(y-1) + x] = b + board[y][x];
			}
		}

	}



	cout << m[n*n] << "\n";





}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: RUNTIME ERROR