#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(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] + 1;
before[i][j] = {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] = {i-1, j};
}
}
}
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 lambda function:
rowords.cpp:57:8: warning: unused variable 'temp' [-Wunused-variable]
57 | int temp = 0;
| ^~~~
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 |
Correct |
22 ms |
34156 KB |
Output is correct |
| 2 |
Correct |
23 ms |
34124 KB |
Output is correct |
| 3 |
Correct |
26 ms |
34156 KB |
Output is correct |
| 4 |
Correct |
23 ms |
34412 KB |
Output is correct |
| 5 |
Correct |
22 ms |
34412 KB |
Output is correct |
| 6 |
Incorrect |
68 ms |
43628 KB |
Output isn't correct |
| 7 |
Correct |
100 ms |
57708 KB |
Output is correct |
| 8 |
Incorrect |
161 ms |
57708 KB |
Output isn't correct |
| 9 |
Correct |
168 ms |
57708 KB |
Output is correct |
| 10 |
Execution timed out |
2100 ms |
57708 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2089 ms |
60140 KB |
Time limit exceeded |
| 12 |
Correct |
169 ms |
63724 KB |
Output is correct |
| 13 |
Correct |
241 ms |
63852 KB |
Output is correct |
| 14 |
Correct |
195 ms |
61164 KB |
Output is correct |
| 15 |
Incorrect |
225 ms |
65516 KB |
Output isn't correct |
| 16 |
Correct |
197 ms |
60012 KB |
Output is correct |
| 17 |
Incorrect |
234 ms |
58732 KB |
Output isn't correct |
| 18 |
Incorrect |
290 ms |
66668 KB |
Output isn't correct |
| 19 |
Correct |
149 ms |
57708 KB |
Output is correct |
| 20 |
Incorrect |
252 ms |
62956 KB |
Output isn't correct |
| 21 |
Correct |
252 ms |
51692 KB |
Output is correct |
| 22 |
Correct |
303 ms |
55660 KB |
Output is correct |
| 23 |
Correct |
316 ms |
58348 KB |
Output is correct |
| 24 |
Incorrect |
344 ms |
59756 KB |
Output isn't correct |
| 25 |
Incorrect |
403 ms |
64236 KB |
Output isn't correct |
