oj.uz

답안 #362062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362062 2021-02-01T16:26:07 Z Sparky_09 원형 문자열 (IZhO13_rowords) C++17
40 / 100
 389 ms 66560 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(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};
      }
      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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 34156 KB Output isn't correct
2 Correct 22 ms 34156 KB Output is correct
3 Correct 22 ms 34156 KB Output is correct
4 Correct 22 ms 34412 KB Output is correct
5 Correct 23 ms 34412 KB Output is correct
6 Incorrect 61 ms 43628 KB Output isn't correct
7 Correct 114 ms 57708 KB Output is correct
8 Incorrect 156 ms 57796 KB Output isn't correct
9 Incorrect 167 ms 57836 KB Output isn't correct
10 Incorrect 133 ms 57708 KB Output isn't correct
11 Incorrect 150 ms 60140 KB Output isn't correct
12 Correct 164 ms 63724 KB Output is correct
13 Incorrect 210 ms 63844 KB Output isn't correct
14 Incorrect 169 ms 61292 KB Output isn't correct
15 Incorrect 194 ms 65516 KB Output isn't correct
16 Correct 203 ms 59992 KB Output is correct
17 Incorrect 235 ms 58604 KB Output isn't correct
18 Incorrect 264 ms 66560 KB Output isn't correct
19 Incorrect 136 ms 57708 KB Output isn't correct
20 Incorrect 236 ms 63084 KB Output isn't correct
21 Correct 253 ms 51692 KB Output is correct
22 Correct 294 ms 55532 KB Output is correct
23 Correct 307 ms 58348 KB Output is correct
24 Incorrect 341 ms 59768 KB Output isn't correct
25 Incorrect 389 ms 64492 KB Output isn't correct