oj.uz

Submission #362060

# Submission time Handle Problem Language Result Execution time Memory
362060 2021-02-01T16:23:36 Z Sparky_09 Round words (IZhO13_rowords) C++17
76 / 100
 395 ms 66540 KB 
#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));
  }
  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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 34156 KB Output isn't correct
2 Correct 27 ms 34156 KB Output is correct
3 Correct 26 ms 34284 KB Output is correct
4 Correct 26 ms 34412 KB Output is correct
5 Correct 27 ms 34412 KB Output is correct
6 Correct 65 ms 43628 KB Output is correct
7 Correct 109 ms 57708 KB Output is correct
8 Incorrect 154 ms 57708 KB Output isn't correct
9 Correct 151 ms 57836 KB Output is correct
10 Correct 135 ms 57796 KB Output is correct
11 Correct 157 ms 60140 KB Output is correct
12 Correct 170 ms 63724 KB Output is correct
13 Correct 204 ms 63852 KB Output is correct
14 Correct 170 ms 61164 KB Output is correct
15 Correct 210 ms 65388 KB Output is correct
16 Correct 176 ms 59884 KB Output is correct
17 Incorrect 219 ms 58732 KB Output isn't correct
18 Correct 262 ms 66540 KB Output is correct
19 Correct 136 ms 57708 KB Output is correct
20 Incorrect 230 ms 63084 KB Output isn't correct
21 Correct 245 ms 51692 KB Output is correct
22 Correct 308 ms 55532 KB Output is correct
23 Correct 305 ms 58348 KB Output is correct
24 Incorrect 336 ms 59756 KB Output isn't correct
25 Incorrect 395 ms 64236 KB Output isn't correct