oj.uz

Submission #124916

# Submission time Handle Problem Language Result Execution time Memory
124916 2019-07-04T07:05:36 Z 송준혁(#3052) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 109 ms 108156 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);
    if (N > M){
        swap(N, M);
        swap(A, B);
    }
    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);
    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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 108152 KB Output is correct
2 Correct 90 ms 108156 KB Output is correct
3 Correct 109 ms 108152 KB Output is correct
4 Incorrect 99 ms 108152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 108152 KB Output is correct
2 Correct 90 ms 108156 KB Output is correct
3 Correct 109 ms 108152 KB Output is correct
4 Incorrect 99 ms 108152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 108152 KB Output is correct
2 Correct 90 ms 108156 KB Output is correct
3 Correct 109 ms 108152 KB Output is correct
4 Incorrect 99 ms 108152 KB Output isn't correct
5 Halted 0 ms 0 KB -