Submission #362056

# Submission time Handle Problem Language Result Execution time Memory
362056 2021-02-01T16:18:56 Z Sparky_09 Round words (IZhO13_rowords) C++17
4 / 100
2000 ms 55020 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());
  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 2078 ms 492 KB Time limit exceeded
3 Execution timed out 2101 ms 748 KB Time limit exceeded
4 Execution timed out 2058 ms 1132 KB Time limit exceeded
5 Execution timed out 2065 ms 1004 KB Time limit exceeded
6 Execution timed out 2078 ms 18796 KB Time limit exceeded
7 Execution timed out 2087 ms 39916 KB Time limit exceeded
8 Execution timed out 2102 ms 39916 KB Time limit exceeded
9 Execution timed out 2098 ms 39916 KB Time limit exceeded
10 Execution timed out 2087 ms 39916 KB Time limit exceeded
11 Execution timed out 2098 ms 43884 KB Time limit exceeded
12 Correct 194 ms 49772 KB Output is correct
13 Execution timed out 2077 ms 49772 KB Time limit exceeded
14 Execution timed out 2097 ms 45548 KB Time limit exceeded
15 Execution timed out 2074 ms 52076 KB Time limit exceeded
16 Execution timed out 2087 ms 43500 KB Time limit exceeded
17 Execution timed out 2076 ms 43116 KB Time limit exceeded
18 Execution timed out 2096 ms 55020 KB Time limit exceeded
19 Execution timed out 2074 ms 39916 KB Time limit exceeded
20 Execution timed out 2099 ms 49260 KB Time limit exceeded
21 Execution timed out 2088 ms 33644 KB Time limit exceeded
22 Execution timed out 2064 ms 39916 KB Time limit exceeded
23 Execution timed out 2096 ms 44012 KB Time limit exceeded
24 Execution timed out 2083 ms 46444 KB Time limit exceeded
25 Execution timed out 2097 ms 53612 KB Time limit exceeded