oj.uz

Submission #288635

# Submission time Handle Problem Language Result Execution time Memory
288635 2020-09-01T17:26:54 Z alexandra_udristoiu Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 43 ms 71036 KB 
#include<iostream>
#include<cstring>
using namespace std;
int n, m, i, j, sol, x, ii, jj, val;
int d[3005][3005], ds[3005][3005];
char a[3005], b[3005];
void solve(int t){
    for(i = n; i >= 1; i--){
        for(j = m; j >= 1; j--){
            if(a[i] == b[j]){
                d[i][j] = 1 + d[i + 1][j + 1];
                x = i + d[i][j] - 1;
                ds[x][j] = max(ds[x][j], d[i][j]);
            }
        }
    }
    for(i = n; i >= 1; i--){
        for(j = 1; j <= m; j++){
            ds[i][j] = max(ds[i][j], ds[i + 1][j - 1] - 1);
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            val = d[i][j] + ds[i - 1][ j + d[i][j] ];
            if(val > sol){
                sol = val;
                if(t == 0){
                    jj = j;
                }
                else{
                    jj = j + val - 1;
                    jj = m - jj + 1;
                }
                ii = i - ds[i - 1][ j + d[i][j] ];
            }
            sol = max(sol, d[i][j] + ds[i - 1][ j + d[i][j] ]);
        }
    }
}
int main(){
    cin>> a + 1;
    n = strlen(a + 1);
    cin>> b + 1;
    m = strlen(b + 1);
    solve(0);
    memset(d, 0, sizeof(d) );
    memset(ds, 0, sizeof(ds) );
    for(i = 1, j = m; i < j; i++, j--){
        swap(b[i], b[j]);
    }
    solve(1);
    cout<< sol <<"\n";
    cout<< ii - 1 <<" "<< jj - 1 <<"\n";
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     cin>> a + 1;
      |           ~~^~~
necklace.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     cin>> b + 1;
      |           ~~^~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 71032 KB Output is correct
2 Correct 42 ms 71032 KB Output is correct
3 Correct 41 ms 71036 KB Output is correct
4 Incorrect 42 ms 71032 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 43 ms 71032 KB Output is correct
2 Correct 42 ms 71032 KB Output is correct
3 Correct 41 ms 71036 KB Output is correct
4 Incorrect 42 ms 71032 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 43 ms 71032 KB Output is correct
2 Correct 42 ms 71032 KB Output is correct
3 Correct 41 ms 71036 KB Output is correct
4 Incorrect 42 ms 71032 KB Output isn't correct
5 Halted 0 ms 0 KB -