#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());
memset(dp, 0x3f, sizeof dp);
for(int i = 0; i <= 2*n; i++){
for(int j = 0; j <= m; j++){
if(i==0 and j==0) continue;
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));
}
reverse(s.begin(), s.end());
memset(dp, 0x3f, sizeof dp);
for(int i = 0; i <= 2*n; i++){
for(int j = 0; j <= m; j++){
if(i==0 and j==0) continue;
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 |
37 ms |
34156 KB |
Output isn't correct |
| 2 |
Correct |
36 ms |
34156 KB |
Output is correct |
| 3 |
Correct |
48 ms |
34284 KB |
Output is correct |
| 4 |
Correct |
55 ms |
34412 KB |
Output is correct |
| 5 |
Correct |
49 ms |
34412 KB |
Output is correct |
| 6 |
Correct |
530 ms |
44268 KB |
Output is correct |
| 7 |
Correct |
591 ms |
58284 KB |
Output is correct |
| 8 |
Incorrect |
697 ms |
58220 KB |
Output isn't correct |
| 9 |
Correct |
656 ms |
58400 KB |
Output is correct |
| 10 |
Correct |
627 ms |
58348 KB |
Output is correct |
| 11 |
Correct |
705 ms |
60700 KB |
Output is correct |
| 12 |
Correct |
777 ms |
64364 KB |
Output is correct |
| 13 |
Correct |
798 ms |
64368 KB |
Output is correct |
| 14 |
Correct |
730 ms |
61676 KB |
Output is correct |
| 15 |
Correct |
892 ms |
66212 KB |
Output is correct |
| 16 |
Correct |
726 ms |
60616 KB |
Output is correct |
| 17 |
Incorrect |
942 ms |
59380 KB |
Output isn't correct |
| 18 |
Correct |
1050 ms |
67316 KB |
Output is correct |
| 19 |
Correct |
669 ms |
58316 KB |
Output is correct |
| 20 |
Incorrect |
911 ms |
63596 KB |
Output isn't correct |
| 21 |
Correct |
1138 ms |
52588 KB |
Output is correct |
| 22 |
Correct |
1335 ms |
56380 KB |
Output is correct |
| 23 |
Correct |
1337 ms |
59172 KB |
Output is correct |
| 24 |
Incorrect |
1458 ms |
60652 KB |
Output isn't correct |
| 25 |
Incorrect |
1510 ms |
65140 KB |
Output isn't correct |
