oj.uz

답안 #101078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101078 2019-03-16T12:04:46 Z choikiwon 원형 문자열 (IZhO13_rowords) C++17
16 / 100
 2000 ms 84184 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;
    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);
    root = 0;
    for(int i = 1; i < N; i++) {
        root++;
        reroot();
        ans = max(ans, N + M - trace(N + i, M));
    }
    printf("%d", ans);
}

Subtask #1
16.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Execution timed out 2067 ms 504 KB Time limit exceeded
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Execution timed out 2058 ms 1016 KB Time limit exceeded
6 Correct 35 ms 18808 KB Output is correct
7 Correct 66 ms 39852 KB Output is correct
8 Execution timed out 2076 ms 39800 KB Time limit exceeded
9 Execution timed out 2070 ms 39800 KB Time limit exceeded
10 Execution timed out 2064 ms 39800 KB Time limit exceeded
11 Runtime error 125 ms 80760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 136 ms 82828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 143 ms 82936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 127 ms 80888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 142 ms 84184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 133 ms 81388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 100 ms 60408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 118 ms 74684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Execution timed out 2041 ms 39800 KB Time limit exceeded
20 Runtime error 120 ms 74872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 77 ms 40184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 83 ms 45020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 99 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 96 ms 54668 KB Execution killed with signal 11 (could be triggered by violating memory limits)