/**
00 00 11 00 00 111111 00000 111111 000000
00 00 1111 0000 11 00 11 11 000000
0000 11 11 00 11 00000 111111 00
00 00 11111111 0000 11 00 11 11 00
00 00 11 11 00 00 111111 00000 11 11 00
**/
#include<bits/stdc++.h>
using namespace std;
#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define pi(a, b) pair<a, b>
#define fast ios::sync_with_stdio(false); cin.tie(0)
void print(int x) {cout << x;}
void print(long long x) {cout << x;}
void print(unsigned x) {cout << x;}
void print(unsigned long long x) {cout << x;}
void print(double x) {cout << fixed << x;}
void print(long double x) {cout << fixed << x;}
void print(char x) {cout << "'" << x << "'";}
void print(string x) {cout << '"' << x << '"';}
void print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void print(const pair<T, V> &x) {cout << '{'; print(x.ff); cout << ", "; print(x.ss); cout << '}';}
template<typename T>
void print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), print(i); cout << "}";}
void _print() {cout << "]" << endl;}
template <typename T, typename... V>
void _print(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifdef TAP
#define bug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define bug(x...)
#endif
void setIO(string s) {
if (sz(s) != 0) {
freopen((s+".inp").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
void setIOusaco(string s) {
if (sz(s) != 0) {
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}
int lcs(string a, string b) {
b += b;
vt<vt<int> > f(sz(a)+1, vt<int>(sz(b)+1, 0));
int res = 0;
fto(j, 0, sz(b)/2 - 1) {
fto(i, 0, sz(a)-1) {
fto(k, 0, sz(b)/2 - 1) {
ckmax(f[i+1][k+1], f[i][k]+(a[i]==b[j+k]));
ckmax(f[i+1][k+1], max(f[i+1][k], f[i][k+1]));
}
res = max(res, f[sz(a)][sz(b)/2]);
}
}
return res;
}
int main() {
#ifndef TAP
//setIO("roundword2013");
//setIOusaco("roundword2013");
#endif
fast;
string s, t;
cin >> s >> t;
int ans1 = lcs(s, t);
reverse(all(t));
int ans2 = lcs(s, t);
cout << max(ans1, ans2) << '\n';
return 0;
}
Compilation message
rowords.cpp: In function 'void setIO(std::string)':
rowords.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | freopen((s+".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rowords.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rowords.cpp: In function 'void setIOusaco(std::string)':
rowords.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rowords.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 6 |
Incorrect |
31 ms |
1100 KB |
Output isn't correct |
| 7 |
Execution timed out |
2093 ms |
8176 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2078 ms |
8176 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2090 ms |
8172 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2090 ms |
8140 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2080 ms |
8908 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2093 ms |
10464 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2092 ms |
10316 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2087 ms |
9292 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2086 ms |
11084 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2084 ms |
9004 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2079 ms |
6840 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2078 ms |
10500 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2089 ms |
8172 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2099 ms |
9492 KB |
Time limit exceeded |
| 21 |
Incorrect |
143 ms |
2252 KB |
Output isn't correct |
| 22 |
Incorrect |
469 ms |
3892 KB |
Output isn't correct |
| 23 |
Incorrect |
1101 ms |
5464 KB |
Output isn't correct |
| 24 |
Incorrect |
1150 ms |
5584 KB |
Output isn't correct |
| 25 |
Execution timed out |
2066 ms |
7432 KB |
Time limit exceeded |
