oj.uz

Submission #340365

# Submission time Handle Problem Language Result Execution time Memory
340365 2020-12-27T13:26:20 Z beksultan04 Round words (IZhO13_rowords) C++14
56 / 100
 2000 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);
            }
        }
    }
    reverse(all(b));
    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 > 4e8){
            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 > 4e8){
            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
56.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 84 ms 1132 KB Output is correct
7 Correct 1574 ms 8212 KB Output is correct
8 Correct 1812 ms 8300 KB Output is correct
9 Incorrect 1684 ms 8300 KB Output isn't correct
10 Incorrect 1609 ms 8300 KB Output isn't correct
11 Incorrect 1589 ms 8212 KB Output isn't correct
12 Execution timed out 2015 ms 8812 KB Time limit exceeded
13 Incorrect 1639 ms 8812 KB Output isn't correct
14 Incorrect 1593 ms 8300 KB Output isn't correct
15 Incorrect 1582 ms 9068 KB Output isn't correct
16 Incorrect 1749 ms 8428 KB Output isn't correct
17 Correct 1560 ms 4848 KB Output is correct
18 Incorrect 1629 ms 7196 KB Output isn't correct
19 Incorrect 1667 ms 8300 KB Output isn't correct
20 Incorrect 1711 ms 7228 KB Output isn't correct
21 Correct 303 ms 1644 KB Output is correct
22 Correct 885 ms 2284 KB Output is correct
23 Correct 1704 ms 3180 KB Output is correct
24 Correct 1807 ms 3180 KB Output is correct
25 Correct 1544 ms 3912 KB Output is correct