oj.uz

Submission #340359

# Submission time Handle Problem Language Result Execution time Memory
340359 2020-12-27T13:23:56 Z beksultan04 Round words (IZhO13_rowords) C++14
48 / 100
 1834 ms 9068 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define eps 1e-12
const int N = 1e5+12,INF=1e9+7;
int dp[2001][2001];
main(){
    string a,b;
    int i,j,n,y,m,cnt=0;
    cin>>a>>b;
    n = a.size();
    m = b.size();

    if (n > m){
        swap(n,m);
        swap(a,b);
    }

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


        a.pb(a[0]);
        a.erase(a.begin());

        for (i=1;i<=n;++i){
            for (j=1;j<=m;++j){
                dp[i][j] = max(dp[i][j-1],dp[i-1][j]);cnt++;
                if (a[i-1]==b[j-1]){
                    dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
        ans = max(ans,dp[n][m]);
        if (cnt > 3e8){
            cout <<ans;
            ret 0;
        }
    }
    reverse(all(b));
    for (y=0;y<n;++y){


        a.pb(a[0]);
        a.erase(a.begin());

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

        ans = max(ans,dp[n][m]);
        if (cnt > 3e8){
            cout <<ans;
            ret 0;
        }
    }


    cout <<ans;
}

Compilation message

rowords.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main(){
      |      ^

Subtask #1
48.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 88 ms 1260 KB Output is correct
7 Correct 1232 ms 8212 KB Output is correct
8 Incorrect 1412 ms 8212 KB Output isn't correct
9 Incorrect 1297 ms 8212 KB Output isn't correct
10 Incorrect 1207 ms 8300 KB Output isn't correct
11 Incorrect 1199 ms 8428 KB Output isn't correct
12 Correct 1518 ms 8812 KB Output is correct
13 Incorrect 1231 ms 8812 KB Output isn't correct
14 Incorrect 1222 ms 8300 KB Output isn't correct
15 Incorrect 1208 ms 9068 KB Output isn't correct
16 Incorrect 1332 ms 8428 KB Output isn't correct
17 Incorrect 1179 ms 4972 KB Output isn't correct
18 Incorrect 1180 ms 7324 KB Output isn't correct
19 Incorrect 1198 ms 8300 KB Output isn't correct
20 Incorrect 1269 ms 7148 KB Output isn't correct
21 Correct 303 ms 1560 KB Output is correct
22 Correct 878 ms 2412 KB Output is correct
23 Correct 1698 ms 3128 KB Output is correct
24 Correct 1834 ms 3128 KB Output is correct
25 Incorrect 1145 ms 3820 KB Output isn't correct