답안 #340357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340357 2020-12-27T13:23:26 Z amunduzbaev 원형 문자열 (IZhO13_rowords) C++14
36 / 100
2000 ms 16256 KB
/** made by amunduzbaev **/
 
#include <bits/stdc++.h>
//~ #include <ext/pb_ds/assoc_container.hpp> 
//~ #include <ext/pb_ds/tree_policy.hpp> 
//~ #include <ext/rope>
 
//~ using namespace __gnu_pbds;
//~ using namespace __gnu_cxx;
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
//~ typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
 
const int N = 2e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int s, n, m, k, t, ans, dp[N][N];
 
void solve(){
	string a, b;
	cin>>a>>b;
	n = sz(b), m = sz(a);
	if(n > m){
		swap(n, m);
		swap(a, b);
	}
	
	b += b;
	for(int i=0;i<n;i++){
		string tmp = string(b.begin() + i, b.begin() + i+ n);
		memset(dp, 0, sizeof dp);
		for(int j=0;j<m;j++){
			for(int l=0;l<n;l++){
				if(j && l && a[j] == tmp[l]) dp[j][l] += dp[j-1][l-1] +1;
				else if(a[j] == tmp[l]) dp[j][l]++;
				if(j) umax(dp[j][l], dp[j-1][l]);
				if(l) umax(dp[j][l], dp[j][l-1]);
				if(j && l) umax(dp[j][l], dp[j-1][l-1]); 
			}
		}
		if(n * m * n >= 5e8){
			cout<<dp[m-1][n-1]<<"\n";
			return;
		}
		umax(ans, dp[m-1][n-1]);
	}
	reverse(all(b));
	
	for(int i=0;i<n;i++){
		string tmp = string(b.begin() + i, b.begin() + i+ n);
		memset(dp, 0, sizeof dp);
		for(int j=0;j<m;j++){
			for(int l=0;l<n;l++){
				if(j && l && a[j] == tmp[l]) dp[j][l] += dp[j-1][l-1] +1;
				else if(a[j] == tmp[l]) dp[j][l]++;
				if(j) umax(dp[j][l], dp[j-1][l]);
				if(l) umax(dp[j][l], dp[j][l-1]);
				if(j && l) umax(dp[j][l], dp[j-1][l-1]); 
			}
		}
		umax(ans, dp[m-1][n-1]);
	}
	
	
	cout<<ans<<endl;
	return;
}
 
int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 16108 KB Output is correct
2 Correct 56 ms 16108 KB Output is correct
3 Correct 101 ms 16108 KB Output is correct
4 Correct 210 ms 16108 KB Output is correct
5 Correct 179 ms 16256 KB Output is correct
6 Correct 564 ms 16128 KB Output is correct
7 Correct 13 ms 16108 KB Output is correct
8 Incorrect 18 ms 16108 KB Output isn't correct
9 Incorrect 16 ms 16108 KB Output isn't correct
10 Incorrect 14 ms 16108 KB Output isn't correct
11 Incorrect 16 ms 16108 KB Output isn't correct
12 Correct 15 ms 16108 KB Output is correct
13 Incorrect 22 ms 16108 KB Output isn't correct
14 Incorrect 17 ms 16108 KB Output isn't correct
15 Incorrect 16 ms 16108 KB Output isn't correct
16 Incorrect 18 ms 16108 KB Output isn't correct
17 Execution timed out 2064 ms 16108 KB Time limit exceeded
18 Incorrect 15 ms 16108 KB Output isn't correct
19 Incorrect 14 ms 16108 KB Output isn't correct
20 Incorrect 17 ms 16108 KB Output isn't correct
21 Correct 1049 ms 16236 KB Output is correct
22 Execution timed out 2082 ms 16108 KB Time limit exceeded
23 Execution timed out 2092 ms 16108 KB Time limit exceeded
24 Execution timed out 2067 ms 16108 KB Time limit exceeded
25 Execution timed out 2027 ms 16108 KB Time limit exceeded