oj.uz

답안 #339787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339787 2020-12-26T08:08:20 Z amunduzbaev 원형 문자열 (IZhO13_rowords) C++14
8 / 100
 2000 ms 16640 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 = 2005;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int s, n, m, k, t, dp[N][N];

void solve(){
	string a, b;
	cin>>a>>b;
	int ans = 0;
	int cnta = 0, cntb = 0, aa = sz(a), bb = sz(b);
	while(cnta < aa){
		string tmpa = string(a.begin() + cnta, a.end()) + string(a.begin(), a.begin()+cnta);
		cntb = 0;
		while(cntb < bb){
			string tmpb = string(b.begin() + cntb, b.end()) + string(b.begin(), b.begin() + cntb);
			
			for(int i=0;i<aa;i++){
				for(int j=0;j<bb;j++){
					if(i && j && tmpa[i] == tmpb[j]) dp[i][j] += dp[i-1][j-1] +1;
					else if(tmpa[i] == tmpb[j]) dp[i][j]++;
					if(i) dp[i][j] = max(dp[i-1][j], dp[i][j]);
					if(j) dp[i][j] = max(dp[i][j-1], dp[i][j]);
					if(i && j) dp[i][j] = max(dp[i][j], dp[i-1][j-1]); 
				}
			}
			
			ans = max(ans, dp[aa-1][bb-1]);
			/*
			for(int i=0;i<aa;i++){
				for(int j=0;j<bb;j++) cout<<dp[i][j]<<" ";
				cout<<"\n";
			}cout<<"\n";
			*/
			memset(dp, 0, sizeof dp);
			cntb++;
		}
		cnta++;
	}
	cout<<ans<<'\n';
	return;
}

int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

Subtask #1
8.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 167 ms 16108 KB Output isn't correct
2 Correct 243 ms 16108 KB Output is correct
3 Correct 864 ms 16236 KB Output is correct
4 Execution timed out 2081 ms 16108 KB Time limit exceeded
5 Execution timed out 2079 ms 16108 KB Time limit exceeded
6 Execution timed out 2056 ms 16236 KB Time limit exceeded
7 Execution timed out 2084 ms 16364 KB Time limit exceeded
8 Execution timed out 2087 ms 16364 KB Time limit exceeded
9 Execution timed out 2084 ms 16620 KB Time limit exceeded
10 Execution timed out 2082 ms 16364 KB Time limit exceeded
11 Execution timed out 2081 ms 16364 KB Time limit exceeded
12 Execution timed out 2040 ms 16492 KB Time limit exceeded
13 Execution timed out 2048 ms 16492 KB Time limit exceeded
14 Execution timed out 2045 ms 16384 KB Time limit exceeded
15 Execution timed out 2087 ms 16236 KB Time limit exceeded
16 Execution timed out 2090 ms 16236 KB Time limit exceeded
17 Execution timed out 2083 ms 16236 KB Time limit exceeded
18 Execution timed out 2088 ms 16108 KB Time limit exceeded
19 Execution timed out 2082 ms 16364 KB Time limit exceeded
20 Execution timed out 2085 ms 16244 KB Time limit exceeded
21 Execution timed out 2084 ms 16236 KB Time limit exceeded
22 Execution timed out 2040 ms 16240 KB Time limit exceeded
23 Execution timed out 2068 ms 16372 KB Time limit exceeded
24 Execution timed out 2035 ms 16368 KB Time limit exceeded
25 Execution timed out 2041 ms 16640 KB Time limit exceeded