oj.uz

Submission #124922

# Submission time Handle Problem Language Result Execution time Memory
124922 2019-07-04T07:14:40 Z 송준혁(#3052) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 1115 ms 108232 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, ans, As, Bs;
char A[3030], B[3030];
int D1[3030][3030];
int D2[3030][3030];
int D3[3030][3030];

int main(){
    scanf("%s", A+1);
    scanf("%s", B+1);
    N = strlen(A+1), M = strlen(B+1);
    bool tf=false;
    if (N > M){
        swap(N, M);
        swap(A, B);
        tf = true;
    }
    for (int i=1-N; i<=M-1; i++){
        for (int j=N; j>0; j--){
            if (i+j < 0 || i+j > M || A[j] != B[i+j]) continue;
            D1[j][i+j] = D1[j+1][i+j+1] + 1;
            D2[j+D1[j][i+j]-1][i+j] = max(D2[j+D1[j][i+j]-1][i+j], D1[j][i+j]);
            D3[j][i+j+D1[j][i+j]-1] = max(D3[j][i+j+D1[j][i+j]-1], D1[j][i+j]);
        }
    }
    for (int i=0; i<=N; i++) for (int j=0; j<=M; j++){
        if (ans < D2[i][j+1] + D3[i+1][j]){
            ans = D2[i][j+1] + D3[i+1][j];
            As = i - D2[i][j+1];
            Bs = j - D3[i+1][j];
        }
    }

    memset(D1, 0, sizeof D1);
    memset(D2, 0, sizeof D2);
    memset(D3, 0, sizeof D3);
    for (int i=1; i<=M/2; i++) swap(B[i], B[M-i+1]);
    for (int i=1-N; i<=M-1; i++){
        for (int j=N; j>0; j--){
            if (i+j < 0 || i+j > M || A[j] != B[i+j]) continue;
            D1[j][i+j] = D1[j+1][i+j+1] + 1;
            D2[j+D1[j][i+j]-1][i+j] = max(D2[j+D1[j][i+j]-1][i+j], D1[j][i+j]);
            D3[j][i+j+D1[j][i+j]-1] = max(D3[j][i+j+D1[j][i+j]-1], D1[j][i+j]);
        }
    }
    for (int i=0; i<=N; i++) for (int j=0; j<=M; j++){
        if (ans < D2[i][j+1] + D3[i+1][j]){
            ans = D2[i][j+1] + D3[i+1][j];
            As = i - D2[i][j+1];
            Bs = M - j - D2[i][j+1];
        }
    }
    printf("%d\n", ans);
    if (tf) printf("%d %d\n", Bs, As);
    else printf("%d %d\n", As, Bs);
    return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", A+1);
     ~~~~~^~~~~~~~~~~
necklace.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", B+1);
     ~~~~~^~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 108136 KB Output is correct
2 Correct 90 ms 108152 KB Output is correct
3 Correct 90 ms 108152 KB Output is correct
4 Correct 91 ms 108152 KB Output is correct
5 Correct 107 ms 108152 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 108136 KB Output is correct
2 Correct 90 ms 108152 KB Output is correct
3 Correct 90 ms 108152 KB Output is correct
4 Correct 91 ms 108152 KB Output is correct
5 Correct 107 ms 108152 KB Output is correct
6 Correct 95 ms 108152 KB Output is correct
7 Correct 101 ms 108068 KB Output is correct
8 Correct 95 ms 108152 KB Output is correct
9 Correct 95 ms 108152 KB Output is correct
10 Correct 96 ms 108152 KB Output is correct
11 Correct 96 ms 108104 KB Output is correct
12 Correct 95 ms 108152 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 108136 KB Output is correct
2 Correct 90 ms 108152 KB Output is correct
3 Correct 90 ms 108152 KB Output is correct
4 Correct 91 ms 108152 KB Output is correct
5 Correct 107 ms 108152 KB Output is correct
6 Correct 95 ms 108152 KB Output is correct
7 Correct 101 ms 108068 KB Output is correct
8 Correct 95 ms 108152 KB Output is correct
9 Correct 95 ms 108152 KB Output is correct
10 Correct 96 ms 108152 KB Output is correct
11 Correct 96 ms 108104 KB Output is correct
12 Correct 95 ms 108152 KB Output is correct
13 Correct 793 ms 108180 KB Output is correct
14 Correct 643 ms 108176 KB Output is correct
15 Correct 1115 ms 108216 KB Output is correct
16 Correct 728 ms 108200 KB Output is correct
17 Correct 314 ms 108152 KB Output is correct
18 Correct 327 ms 108164 KB Output is correct
19 Correct 456 ms 108168 KB Output is correct
20 Correct 784 ms 108232 KB Output is correct
21 Correct 776 ms 108180 KB Output is correct