oj.uz

Submission #101080

# Submission time Handle Problem Language Result Execution time Memory
101080 2019-03-16T12:10:26 Z choikiwon Round words (IZhO13_rowords) C++17
36 / 100
 144 ms 84060 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;
        if(nr < root) nr = root;
        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;
    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 3 ms 504 KB Output isn't correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 0 ms 1144 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 40 ms 18808 KB Output is correct
7 Correct 68 ms 39800 KB Output is correct
8 Incorrect 113 ms 39820 KB Output isn't correct
9 Correct 114 ms 39880 KB Output is correct
10 Correct 114 ms 39944 KB Output is correct
11 Runtime error 126 ms 80712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 120 ms 82808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 131 ms 82912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 125 ms 80888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 125 ms 84060 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 144 ms 81308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 101 ms 60408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 115 ms 74748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Correct 89 ms 39800 KB Output is correct
20 Runtime error 123 ms 74832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 84 ms 40312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 84 ms 44972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 88 ms 49896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 89 ms 49784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 93 ms 54708 KB Execution killed with signal 11 (could be triggered by violating memory limits)