oj.uz

답안 #362057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362057 2021-02-01T16:20:00 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[8200][2100];
pii before[8200][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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Execution timed out 2079 ms 492 KB Time limit exceeded
3 Execution timed out 2087 ms 748 KB Time limit exceeded
4 Execution timed out 2076 ms 1132 KB Time limit exceeded
5 Execution timed out 2075 ms 1004 KB Time limit exceeded
6 Execution timed out 2045 ms 18796 KB Time limit exceeded
7 Execution timed out 2069 ms 39916 KB Time limit exceeded
8 Execution timed out 2084 ms 39916 KB Time limit exceeded
9 Execution timed out 2076 ms 39916 KB Time limit exceeded
10 Execution timed out 2088 ms 39916 KB Time limit exceeded
11 Execution timed out 2047 ms 43884 KB Time limit exceeded
12 Correct 194 ms 49772 KB Output is correct
13 Execution timed out 2085 ms 49772 KB Time limit exceeded
14 Execution timed out 2068 ms 45548 KB Time limit exceeded
15 Execution timed out 2066 ms 52076 KB Time limit exceeded
16 Execution timed out 2081 ms 43628 KB Time limit exceeded
17 Execution timed out 2093 ms 42988 KB Time limit exceeded
18 Execution timed out 2077 ms 55020 KB Time limit exceeded
19 Execution timed out 2091 ms 39916 KB Time limit exceeded
20 Execution timed out 2091 ms 49132 KB Time limit exceeded
21 Execution timed out 2061 ms 33792 KB Time limit exceeded
22 Execution timed out 2085 ms 39788 KB Time limit exceeded
23 Execution timed out 2077 ms 44012 KB Time limit exceeded
24 Execution timed out 2081 ms 46444 KB Time limit exceeded
25 Execution timed out 2086 ms 53484 KB Time limit exceeded