oj.uz

답안 #339786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339786 2020-12-26T08:08:03 Z tengiz05 원형 문자열 (IZhO13_rowords) C++17
20 / 100
 38 ms 15468 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 2005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k;
string a, b;
int ans;
int dp[2005][4005];
void do_it_now(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m*2;j++){
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			//~ else dp[i][j] = max(dp[i-1][j]-dp[i-1][j-m-1], dp[i][j-1]-dp[i][j-m-1]);
			if(a[i-1] == b[j-1]){
				chmax(dp[i][j], dp[i-1][j-1]+1);
				//~ else chmax(dp[i][j], dp[i-1][j-1]+1 - dp[i][j-m]);
			}
		}
	}
	chmax(ans, dp[n][m]);
	for(int i=1;i<=n;i++){
		for(int j=m+1;j<=m*2;j++){
			if(a[i-1] == b[j-1])
				chmax(ans, dp[i][j]-dp[i-1][j-m-1]);
		}
	}
}
void solve(int test_case){
	int i, j;
	cin >> a >> b;
	if(a.length() > b.length())swap(a,b);
	b += b;
	n = a.length(), m = b.length()/2;
	
	do_it_now();
	reverse(all(b));
	do_it_now();
	cout << ans << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

rowords.cpp: In function 'void solve(int)':
rowords.cpp:40:6: warning: unused variable 'i' [-Wunused-variable]
   40 |  int i, j;
      |      ^
rowords.cpp:40:9: warning: unused variable 'j' [-Wunused-variable]
   40 |  int i, j;
      |         ^

Subtask #1
20.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 0 ms 364 KB Output isn't correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Correct 1 ms 492 KB Output is correct
5 Incorrect 1 ms 492 KB Output isn't correct
6 Correct 3 ms 1516 KB Output is correct
7 Correct 26 ms 12140 KB Output is correct
8 Incorrect 35 ms 12140 KB Output isn't correct
9 Incorrect 31 ms 12140 KB Output isn't correct
10 Incorrect 27 ms 12140 KB Output isn't correct
11 Incorrect 29 ms 13184 KB Output isn't correct
12 Correct 32 ms 14700 KB Output is correct
13 Incorrect 36 ms 14684 KB Output isn't correct
14 Incorrect 30 ms 13292 KB Output isn't correct
15 Incorrect 34 ms 15468 KB Output isn't correct
16 Incorrect 38 ms 13036 KB Output isn't correct
17 Incorrect 21 ms 9068 KB Output isn't correct
18 Incorrect 32 ms 13932 KB Output isn't correct
19 Incorrect 26 ms 12140 KB Output isn't correct
20 Incorrect 34 ms 13036 KB Output isn't correct
21 Incorrect 7 ms 2668 KB Output isn't correct
22 Incorrect 11 ms 4204 KB Output isn't correct
23 Incorrect 15 ms 5868 KB Output isn't correct
24 Incorrect 16 ms 5868 KB Output isn't correct
25 Incorrect 21 ms 7404 KB Output isn't correct