oj.uz

Submission #47552

# Submission time Handle Problem Language Result Execution time Memory
47552 2018-05-05T03:30:59 Z ngkan146 Round words (IZhO13_rowords) C++11
36 / 100
 80 ms 32784 KB 
#include <bits/stdc++.h>
using namespace std;
string t[2], s[2];
int dp[4005][4005];
int lca(string &a, string &b){
    for(int i=1;i<a.size();i++){
        for(int j=1;j<b.size();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);
        }
    }
    return dp[a.size()-1][b.size()-1];
}
int main(){
    cin >> t[0] >> t[1];
    s[0] = '0' + t[0];
    s[1] = '0' + t[1];

    int tmp = lca(s[0], s[1]);
    s[0] = '0' + t[0] + t[0];
    s[1] = '0' + t[1] + t[1];
    tmp = lca(s[0], s[1]) - tmp;

    reverse(t[0].begin(), t[0].end());

    s[0] = '0' + t[0];
    s[1] = '0' + t[1];

    int tmp2 = lca(s[0], s[1]);
    s[0] = '0' + t[0] + t[0];
    s[1] = '0' + t[1] + t[1];
    tmp2 = lca(s[0], s[1]) - tmp2;
    cout << max(tmp, tmp2);
}

Compilation message

rowords.cpp: In function 'int lca(std::__cxx11::string&, std::__cxx11::string&)':
rowords.cpp:6:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<a.size();i++){
                 ~^~~~~~~~~
rowords.cpp:7:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<b.size();j++){
                     ~^~~~~~~~~

Subtask #1
36.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 504 KB Output isn't correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 16 ms 9976 KB Output is correct
7 Correct 56 ms 24132 KB Output is correct
8 Incorrect 61 ms 24056 KB Output isn't correct
9 Incorrect 60 ms 24056 KB Output isn't correct
10 Incorrect 57 ms 24064 KB Output isn't correct
11 Incorrect 62 ms 26360 KB Output isn't correct
12 Correct 80 ms 30072 KB Output is correct
13 Incorrect 75 ms 30200 KB Output isn't correct
14 Incorrect 69 ms 27560 KB Output isn't correct
15 Incorrect 75 ms 31608 KB Output isn't correct
16 Incorrect 65 ms 26232 KB Output isn't correct
17 Incorrect 53 ms 24952 KB Output isn't correct
18 Correct 74 ms 32784 KB Output is correct
19 Incorrect 57 ms 24056 KB Output isn't correct
20 Incorrect 70 ms 29304 KB Output isn't correct
21 Incorrect 31 ms 18040 KB Output isn't correct
22 Incorrect 40 ms 21880 KB Output isn't correct
23 Correct 48 ms 24700 KB Output is correct
24 Correct 50 ms 25976 KB Output is correct
25 Incorrect 62 ms 30456 KB Output isn't correct