oj.uz

답안 #339785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339785 2020-12-26T08:03:26 Z tengiz05 원형 문자열 (IZhO13_rowords) C++17
20 / 100
 43 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]);
			}
			//~ cout << dp[i][j] << ' ';
		}
		//~ cout << '\n';
	}
	//~ cout << '\n';
	chmax(ans, dp[n][m]);
	for(int j=m+1;j<=m*2;j++){
		chmax(ans, dp[n][j]-dp[n][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 1 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 23 ms 12140 KB Output is correct
8 Incorrect 28 ms 12140 KB Output isn't correct
9 Incorrect 25 ms 12140 KB Output isn't correct
10 Incorrect 23 ms 12140 KB Output isn't correct
11 Incorrect 26 ms 12928 KB Output isn't correct
12 Correct 43 ms 14700 KB Output is correct
13 Incorrect 43 ms 14700 KB Output isn't correct
14 Incorrect 26 ms 13292 KB Output isn't correct
15 Incorrect 29 ms 15468 KB Output isn't correct
16 Incorrect 31 ms 13036 KB Output isn't correct
17 Incorrect 18 ms 9068 KB Output isn't correct
18 Incorrect 30 ms 13932 KB Output isn't correct
19 Incorrect 22 ms 12140 KB Output isn't correct
20 Incorrect 37 ms 13036 KB Output isn't correct
21 Incorrect 6 ms 2668 KB Output isn't correct
22 Incorrect 10 ms 4204 KB Output isn't correct
23 Incorrect 13 ms 5868 KB Output isn't correct
24 Incorrect 14 ms 5868 KB Output isn't correct
25 Incorrect 18 ms 7404 KB Output isn't correct