oj.uz

Submission #101084

# Submission time Handle Problem Language Result Execution time Memory
101084 2019-03-16T12:17:36 Z choikiwon Round words (IZhO13_rowords) C++17
76 / 100
 195 ms 55032 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;

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
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 34 ms 18808 KB Output is correct
7 Correct 66 ms 39800 KB Output is correct
8 Incorrect 104 ms 39800 KB Output isn't correct
9 Correct 107 ms 39828 KB Output is correct
10 Correct 95 ms 39800 KB Output is correct
11 Correct 112 ms 43768 KB Output is correct
12 Correct 139 ms 49016 KB Output is correct
13 Correct 135 ms 49016 KB Output is correct
14 Correct 109 ms 45436 KB Output is correct
15 Correct 127 ms 51192 KB Output is correct
16 Correct 120 ms 43256 KB Output is correct
17 Incorrect 113 ms 43000 KB Output isn't correct
18 Correct 152 ms 55032 KB Output is correct
19 Correct 90 ms 39800 KB Output is correct
20 Incorrect 146 ms 49144 KB Output isn't correct
21 Correct 99 ms 33656 KB Output is correct
22 Correct 129 ms 39920 KB Output is correct
23 Correct 150 ms 44024 KB Output is correct
24 Incorrect 161 ms 46552 KB Output isn't correct
25 Incorrect 195 ms 53644 KB Output isn't correct