oj.uz

Submission #101085

# Submission time Handle Problem Language Result Execution time Memory
101085 2019-03-16T12:23:50 Z choikiwon Round words (IZhO13_rowords) C++17
0 / 100
 405 ms 55136 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 2010;

int N, M;
string S, T;
int len[MN << 1][MN];
pii par[MN << 1][MN];
int root, ans;

int trace(int r, int c) {
    int ret = 0;
    while(r != root || c) {
        int nr = par[r][c].first;
        int nc = par[r][c].second;
        r = nr;
        c = nc;
        ret++;
    }
    return ret;
}

void reroot() {
    int i = root;
    int j = 1;
    while(j <= M && par[i][j] != pii(i - 1, j - 1)) j++;
    if(j > M) return;
    par[i][j] = pii(i, j - 1);
    while(i < 2 * N && j < M) {
        if(par[i + 1][j] == pii(i, j)) {
            i++;
            par[i][j] = pii(i, j - 1);
        }
        else if(par[i + 1][j + 1] == pii(i, j)) {
            i++;
            j++;
            par[i][j] = pii(i, j - 1);
        }
        else j++;
    }
    while(i < 2 * N && par[i + 1][j] == pii(i, j)) {
        i++;
        par[i][j] = pii(i, j - 1);
    }
}

void solve() {
    for(int i = 0; i <= 2 * N; i++) {
        for(int j = 0; j <= M; j++) {
            if(!i && !j) continue;

            len[i][j] = 1e9;
            if(j && len[i][j] > len[i][j - 1] + 1) len[i][j] = len[i][j - 1] + 1, par[i][j] = pii(i, j - 1);
            if(i && j && S[(i - 1) % N] == T[j - 1] && len[i][j] > len[i - 1][j - 1] + 1) len[i][j] = len[i - 1][j - 1] + 1, par[i][j] = pii(i - 1, j - 1);
            if(i && len[i][j] > len[i - 1][j] + 1) len[i][j] = len[i - 1][j] + 1, par[i][j] = pii(i - 1, j);
        }
    }

    root = 0;
    ans = max(ans, N + M - trace(N, M));
    for(int i = 1; i < N; i++) {
        root++;
        reroot();
        ans = max(ans, N + M - trace(N + i, M));
    }

    cout << ans << endl;
}

int main() {
    std::ios::sync_with_stdio(false);

    cin >> S >> T;

    N = S.size();
    M = T.size();

    solve();
    reverse(T.begin(), T.end());
    solve();

    cout << ans;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Incorrect 2 ms 760 KB Output isn't correct
4 Incorrect 3 ms 1144 KB Output isn't correct
5 Incorrect 3 ms 1016 KB Output isn't correct
6 Incorrect 54 ms 18940 KB Output isn't correct
7 Incorrect 106 ms 39928 KB Output isn't correct
8 Incorrect 177 ms 39800 KB Output isn't correct
9 Incorrect 182 ms 39800 KB Output isn't correct
10 Incorrect 170 ms 39792 KB Output isn't correct
11 Incorrect 170 ms 43768 KB Output isn't correct
12 Incorrect 200 ms 49016 KB Output isn't correct
13 Incorrect 257 ms 49016 KB Output isn't correct
14 Incorrect 192 ms 45496 KB Output isn't correct
15 Incorrect 219 ms 51192 KB Output isn't correct
16 Incorrect 218 ms 43380 KB Output isn't correct
17 Incorrect 194 ms 43124 KB Output isn't correct
18 Incorrect 265 ms 55136 KB Output isn't correct
19 Incorrect 149 ms 39800 KB Output isn't correct
20 Incorrect 247 ms 49368 KB Output isn't correct
21 Incorrect 182 ms 33656 KB Output isn't correct
22 Incorrect 219 ms 39916 KB Output isn't correct
23 Incorrect 257 ms 44244 KB Output isn't correct
24 Incorrect 310 ms 46456 KB Output isn't correct
25 Incorrect 405 ms 53540 KB Output isn't correct