oj.uz

Submission #356833

# Submission time Handle Problem Language Result Execution time Memory
356833 2021-01-23T19:46:05 Z nicolaalexandra Round words (IZhO13_rowords) C++14
4 / 100
 48 ms 16952 KB 
#include <bits/stdc++.h>
#define DIM 1010
using namespace std;

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

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

    memset (dp_left,0,sizeof dp_left);
    memset (dp_right,0,sizeof dp_right);

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

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

    for (i=1;i<=n+1;i++)
        for (j=1;j<=m+1;j++)
            sol = max (sol,dp_right[i][j] + dp_left[i-1][j-1]);

}

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];

    solve (a,b);
    solve (a,b2);
    solve (a2,b);
    solve (a2,b2);

    cout<<sol;


    return 0;
}

Compilation message

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

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8300 KB Output isn't correct
2 Incorrect 7 ms 8300 KB Output isn't correct
3 Incorrect 7 ms 8300 KB Output isn't correct
4 Incorrect 9 ms 8300 KB Output isn't correct
5 Correct 8 ms 8300 KB Output is correct
6 Incorrect 11 ms 8300 KB Output isn't correct
7 Incorrect 42 ms 8428 KB Output isn't correct
8 Incorrect 47 ms 8300 KB Output isn't correct
9 Incorrect 48 ms 8300 KB Output isn't correct
10 Incorrect 43 ms 8300 KB Output isn't correct
11 Runtime error 21 ms 16876 KB Execution killed with signal 11
12 Incorrect 10 ms 8300 KB Output isn't correct
13 Incorrect 9 ms 8300 KB Output isn't correct
14 Runtime error 21 ms 16876 KB Execution killed with signal 11
15 Incorrect 11 ms 8300 KB Output isn't correct
16 Runtime error 21 ms 16876 KB Execution killed with signal 11
17 Runtime error 19 ms 16876 KB Execution killed with signal 11
18 Runtime error 20 ms 16876 KB Execution killed with signal 11
19 Incorrect 42 ms 8300 KB Output isn't correct
20 Runtime error 21 ms 16952 KB Execution killed with signal 11
21 Runtime error 17 ms 16876 KB Execution killed with signal 11
22 Runtime error 18 ms 16896 KB Execution killed with signal 11
23 Runtime error 18 ms 16876 KB Execution killed with signal 11
24 Runtime error 19 ms 16876 KB Execution killed with signal 11
25 Runtime error 19 ms 16876 KB Execution killed with signal 11