Ruudukko

#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef int ll;

ll n;
ll t;

int main() {

	ios_base::sync_with_stdio(false);

	cin >> n;
	t = n*n;

	ll ruudut[t];
	ll scores[t];
	ll dirs[t];

	string line;
	for (ll i = 0; i < t; ++i) {
		static char temp;
		cin >> temp;
		ruudut[i] = temp - 'A';
	}

	for (ll k = 0; k < 2 * n; ++k) {
		for (ll x = 0; x < n; ++x) {
			for (ll y = 0; y < n; ++y) {
				if (x + y != k) continue;
				ll i = y * n + x;
				ll own = ruudut[i];
				if (i % n == 0 && i / n == 0) {
					scores[i] = own;
					dirs[i] = 2;
				} else if (i % n == 0) {
					scores[i] = own + scores[i - n];
					dirs[i] = 1;
				} else if (i / n == 0) {
					scores[i] = own + scores[i - 1];
					dirs[i] = 0;
				} else {
					ll vert = own + scores[i - n];
					ll hori = own + scores[i - 1];
					if (vert < hori) {
						scores[i] = vert;
						dirs[i] = 1;
					} else {
						scores[i] = hori;
						dirs[i] = 0;
					}
				}
			}
		}
	}

	char res[2 * n - 1];
	ll j = 2 * n - 2;
	ll i = t - 1;
	res[0] = ruudut[0] + 'A';
	while (i != 0) {
		res[j] = ruudut[i] + 'A';
		--j;
		if (dirs[i] == 0) {
			i -= 1;
		} else if (dirs[i] == 1) {
			i -= n;
		}
	}

	for (int i = 0; i < 2 * n - 1; ++i) {
		cout << res[i];
	}
	cout << '\n';

	return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: WRONG ANSWER