oj.uz

Submission #101082

# Submission time Handle Problem Language Result Execution time Memory
101082 2019-03-16T12:14:43 Z choikiwon Round words (IZhO13_rowords) C++17
36 / 100
 135 ms 84128 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));
    }
    cout << 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 3 ms 760 KB Output is correct
4 Correct 3 ms 1064 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 34 ms 18812 KB Output is correct
7 Correct 66 ms 39856 KB Output is correct
8 Incorrect 102 ms 39804 KB Output isn't correct
9 Correct 110 ms 39932 KB Output is correct
10 Correct 93 ms 39800 KB Output is correct
11 Runtime error 125 ms 80760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 135 ms 82936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 132 ms 83036 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 126 ms 84128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 133 ms 81408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 100 ms 60388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 118 ms 74716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Correct 87 ms 39800 KB Output is correct
20 Runtime error 121 ms 74844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 77 ms 40352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 82 ms 45048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 88 ms 49784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 88 ms 49912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 95 ms 54660 KB Execution killed with signal 11 (could be triggered by violating memory limits)