oj.uz

답안 #362058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362058 2021-02-01T16:21:44 Z Sparky_09 원형 문자열 (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());
  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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 100.0

# 결과 실행 시간 메모리 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