oj.uz

Submission #357660

# Submission time Handle Problem Language Result Execution time Memory
357660 2021-01-24T11:29:08 Z nicolaalexandra Round words (IZhO13_rowords) C++14
24 / 100
 100 ms 32876 KB 
#include <bits/stdc++.h>
#define DIM 2010
using namespace std;

char a[DIM],b[DIM],a2[DIM],b2[DIM];
int dp[DIM][DIM];
int n,m,i,j,sol;

void solve (char a[], char b[]){

    memset (dp,0,sizeof dp);

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            dp[i][j] = max (dp[i-1][j],dp[i][j-1]);
            if (a[i] == b[j])
                dp[i][j] = max (dp[i][j],dp[i-1][j-1] + 1);
        }

    for (int poz=1;poz<=n;poz++){

        int i = poz, j = m, cnt = 0;
        while (i > max(0,poz - n/2) && j >= 1){
            if (a[i] == b[j]){
                cnt++;
                i--, j--;
            } else {
                if (dp[i][j-1] >= dp[i-1][j])
                    j--;
                else i--;
            }
        }
        sol = max (sol,cnt);
    }
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>a+1>>b+1;
    n = strlen (a+1), m = strlen (b+1);

    for (i=1;i<=n;i++)
        a2[n-i+1] = a[i];
    for (i=1;i<=m;i++)
        b2[m-i+1] = b[i];

    for (i=1;i<=n;i++)
        a[i+n] = a[i];
    n *= 2;
    solve (a,b);
    solve (a,b2);

    for (i=1;i<=n/2;i++)
        a2[i+n/2] = a2[i];
    solve (a2,b);

    cout<<sol;


    return 0;
}

Compilation message

rowords.cpp: In function 'int main()':
rowords.cpp:42:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     cin>>a+1>>b+1;
      |          ~^~
rowords.cpp:42:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     cin>>a+1>>b+1;
      |               ~^~

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16108 KB Output is correct
2 Correct 12 ms 16108 KB Output is correct
3 Correct 12 ms 16108 KB Output is correct
4 Correct 13 ms 16108 KB Output is correct
5 Incorrect 13 ms 16256 KB Output isn't correct
6 Correct 34 ms 16108 KB Output is correct
7 Correct 72 ms 16108 KB Output is correct
8 Incorrect 75 ms 16108 KB Output isn't correct
9 Incorrect 99 ms 16108 KB Output isn't correct
10 Incorrect 97 ms 16236 KB Output isn't correct
11 Runtime error 38 ms 32748 KB Execution killed with signal 11
12 Runtime error 41 ms 32748 KB Execution killed with signal 11
13 Runtime error 38 ms 32748 KB Execution killed with signal 11
14 Runtime error 37 ms 32748 KB Execution killed with signal 11
15 Runtime error 38 ms 32748 KB Execution killed with signal 11
16 Runtime error 46 ms 32876 KB Execution killed with signal 11
17 Runtime error 36 ms 32620 KB Execution killed with signal 11
18 Runtime error 36 ms 32748 KB Execution killed with signal 11
19 Incorrect 100 ms 16108 KB Output isn't correct
20 Runtime error 39 ms 32748 KB Execution killed with signal 11
21 Runtime error 32 ms 32620 KB Execution killed with signal 11
22 Runtime error 32 ms 32620 KB Execution killed with signal 11
23 Runtime error 32 ms 32620 KB Execution killed with signal 11
24 Runtime error 33 ms 32620 KB Execution killed with signal 11
25 Runtime error 33 ms 32620 KB Execution killed with signal 11