oj.uz

Submission #101081

# Submission time Handle Problem Language Result Execution time Memory
101081 2019-03-16T12:12:29 Z choikiwon Round words (IZhO13_rowords) C++17
36 / 100
 140 ms 84088 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][MN];
pii par[MN][MN];
int root;

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);
    }
}

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

    cin >> S >> T;

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

    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);
        }
    }

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

Subtask #1
36.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 35 ms 18808 KB Output is correct
7 Correct 66 ms 39800 KB Output is correct
8 Incorrect 104 ms 39824 KB Output isn't correct
9 Correct 104 ms 39800 KB Output is correct
10 Correct 95 ms 39800 KB Output is correct
11 Runtime error 125 ms 80632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 121 ms 82856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 130 ms 82884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 140 ms 80760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 139 ms 84088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 139 ms 81428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 114 ms 60380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 125 ms 74744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Correct 93 ms 39832 KB Output is correct
20 Runtime error 122 ms 74876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 81 ms 40312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 89 ms 45048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 87 ms 49912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 87 ms 49912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 93 ms 54520 KB Execution killed with signal 11 (could be triggered by violating memory limits)