oj.uz

답안 #362090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362090 2021-02-01T17:34:02 Z Sparky_09 원형 문자열 (IZhO13_rowords) C++17
96 / 100
 407 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++;
      }
    }
  };
  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;
      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] = {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] = {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
96.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 34156 KB Output is 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 Incorrect 22 ms 34412 KB Output isn't correct
6 Correct 62 ms 43628 KB Output is correct
7 Correct 101 ms 57836 KB Output is correct
8 Correct 181 ms 57708 KB Output is correct
9 Correct 212 ms 57836 KB Output is correct
10 Correct 185 ms 57708 KB Output is correct
11 Correct 175 ms 60172 KB Output is correct
12 Correct 206 ms 63852 KB Output is correct
13 Correct 265 ms 63872 KB Output is correct
14 Correct 198 ms 61164 KB Output is correct
15 Correct 235 ms 65388 KB Output is correct
16 Correct 221 ms 60012 KB Output is correct
17 Correct 233 ms 58604 KB Output is correct
18 Correct 309 ms 66540 KB Output is correct
19 Correct 150 ms 57708 KB Output is correct
20 Correct 273 ms 63084 KB Output is correct
21 Correct 256 ms 51820 KB Output is correct
22 Correct 300 ms 55704 KB Output is correct
23 Correct 321 ms 58476 KB Output is correct
24 Correct 356 ms 59884 KB Output is correct
25 Correct 407 ms 64364 KB Output is correct