Ruudukko

#include <bits/stdc++.h>

using namespace std;

const int N = 501;

struct Vec
{
public:
    int x;
    int y;
    Vec(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
    Vec()
    {
        this->x = 0;
        this->y = 0;
    }
};

int n;
string m[N];
string r = "";
Vec v[N][N];

int main()
{
    cin>>n;
    string s;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        m[i] = s;
    }

    n--;
    for(int x=n;x>=0;x--)
    {
        for(int y=n;y>=0;y--)
        {
            if(x==n && y==n) continue;
            else if(x==n)
            {
                v[x][y] = Vec(x,y+1);
            }
            else if(y==n)
            {
                v[x][y] = Vec(x+1,y);
            }
            else
            {
                Vec rpos = Vec(x,y+1);
                Vec dpos = Vec(x+1,y);
                while(rpos.x<=n && rpos.y<=n && dpos.x<=n && dpos.y<=n && m[rpos.x][rpos.y] == m[dpos.x][dpos.y])
                {
                    rpos = v[rpos.x][rpos.y];
                    dpos = v[dpos.x][dpos.y];
                }
                if(m[rpos.x][rpos.y] < m[dpos.x][dpos.y]) v[x][y] = Vec(x,y+1);
                else v[x][y] = Vec(x+1,y);
            }
        }
    }

    Vec vec = Vec(0,0);
    for(int i=0;i<n*2+1;i++)
    {
        cout<<m[vec.x][vec.y];
        vec = v[vec.x][vec.y];
    }
}

Test 1

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED