#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
void usaco(string s){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
int n, m, start=0, ans = 0;
string s, t;
int dp[4100][2100];
pii before[4100][2100];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
freopen("input.txt", "r", stdin);
#endif
cin >> s >> t;
cerr << s << ' ' << t << '\n';
n = s.size(); m = t.size();
//for(int i = 0; i < 4100; i++) for(int j = 0; j < 2100; j++) dp[i][j] = (int)1e9;
//dp[0][0] = 0;
for(int i = 0; i <= 2*n; i++){
for(int j = 0; j <= m; j++){
if(i==0 and j==0) continue;
dp[i][j] = 1e9;
if(j > 0 and dp[i][j] > dp[i][j-1] + 1){
dp[i][j] = dp[i][j-1] + 1;
before[i][j] = make_pair(i, j-1);
}
if(i > 0 and j > 0 and s[(i - 1)%n] == t[j-1] and dp[i][j] > dp[i-1][j-1] + 1){
dp[i][j] = dp[i-1][j-1] + 1;
before[i][j] = make_pair(i-1, j-1);
}
if(i > 0 and dp[i][j] > dp[i-1][j] + 1){
dp[i][j] = dp[i-1][j] + 1;
before[i][j] = make_pair(i-1, j);
}
//cerr << before[i][j].first << ' ' << before[i][j].second << ' ' << i << ' ' << j << '\n';
}
}
auto back = [&](int n1, int m1){
int sub = 0;
//int temp = 0;
//cerr << n1 << ' ' << m1 << '\n';
while(n1 != start or m1){
n1 = before[n1][m1].first; m1 = before[n1][m1].second;
sub++;
//if(temp<10)
//cerr << "here" << ' ' << n1 << ' ' << m1 << '\n'; //here is the error
//temp++;
}
//cerr<<"done";
return sub;
};
auto newstart = [&](){
int i = start, j = 1;
while(j <= m and (before[i][j] != make_pair(i - 1, j - 1))){
j++;
}
if(j > m){
return;
}
before[i][j] = make_pair(i, j - 1);
//move one forward start is ahead now, we process next set
while(i < 2*n and j < m){
if(before[i+1][j] == make_pair(i, j)){
i++;
before[i][j] = make_pair(i, j-1);
}
else if(before[i+1][j+1] == make_pair(i, j)){
i++; j++;
before[i][j] = make_pair(i, j-1);
}
else{
j++;
}
}
while(i < 2*n and before[i+1][j] == make_pair(i, j)){
i++; before[i][j] = make_pair(i, j-1);
}
};
start = 0;
ans = max(ans, n + m - back(n, m));
for(int i = 1; i < n; i++){
start++; newstart();
ans = max(ans, n+m-back(n+i,m));
}
reverse(t.begin(), t.end());
dp[0][0] = 0;
for(int i = 0; i <= 2*n; i++){
for(int j = 0; j <= m; j++){
if(i==0 and j==0) continue;
dp[i][j]=1e9;
if(i > 0 and dp[i][j] > dp[i-1][j] + 1){
dp[i][j] = dp[i-1][j] + 1;
before[i][j] = {i-1, j};
}
if(j > 0 and dp[i][j] > dp[i][j-1] + 1){
dp[i][j] = dp[i][j-1] + 1;
before[i][j] = {i, j-1};
}
if(i > 0 and j > 0 and s[(i - 1)%n] == t[j-1] and dp[i][j] > dp[i-1][j-1] + 1){
dp[i][j] = dp[i-1][j] + 1;
before[i][j] = {i-1, j-1};
}
}
}
start = 0;
ans = max(ans, n + m - back(n, m));
for(int i = 1; i < n; i++){
start++; newstart();
ans = max(ans, n+m-back(n+i,m));
}
cout << ans << '\n';
}
Compilation message
rowords.cpp: In function 'void usaco(std::string)':
rowords.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
13 | freopen((s+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rowords.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
14 | freopen((s+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Execution timed out |
2076 ms |
492 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2080 ms |
748 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2037 ms |
1132 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2089 ms |
1004 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2029 ms |
18796 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2082 ms |
39916 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2089 ms |
39916 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2045 ms |
39916 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2070 ms |
39916 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2081 ms |
43884 KB |
Time limit exceeded |
| 12 |
Correct |
192 ms |
49772 KB |
Output is correct |
| 13 |
Execution timed out |
2068 ms |
49772 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2089 ms |
45548 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2039 ms |
52076 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2081 ms |
43500 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2088 ms |
42988 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2084 ms |
55020 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2082 ms |
39916 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2093 ms |
49132 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2079 ms |
33644 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2093 ms |
39788 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2075 ms |
44012 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2098 ms |
46444 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2087 ms |
53612 KB |
Time limit exceeded |
