Submission #288645

#	Time	Username	Problem	Language	Result	Execution time	Memory
288645		alexandra_udristoiu	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	85 / 85	223 ms	71160 KiB

necklace

#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 = 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 (stderr)

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

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40