oj.uz

Submission #584488

# Submission time Handle Problem Language Result Execution time Memory
584488 2022-06-27T13:04:33 Z amunduzbaev Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 312 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
//~ #define int ll

const int N = 3005;
int is[N][N], d[N][N], u[N][N], ur[N][N], dl[N][N];

ar<int, 3> solve(string a, string b){
	ar<int, 3> res {};
	int n = a.size(), m = b.size();
	//~ if(n > m) swap(n, m), swap(a, b);
	
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			int mx = 0;
			for(int k=1;k<=min(i, m - j);k++){
				string s = string(a.begin() + i - k, a.begin() + i);
				string t = string(b.begin() + j, b.begin() + j + k);
				if(s == t){
					mx = k;
				}
			}
			
			for(int k=0;k<=min(j, n - i);k++){
				string s = string(a.begin() + i, a.begin() + i + k);
				string t = string(b.begin() + j - k, b.begin() + j);
				if(s == t){
					res = max(res, {mx + k, i - mx, j - k});
				}
			}
		}
	}
	
	return res;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	string a, b; cin>>a>>b;
	ar<int, 3> res {};
	res = solve(a, b);
	reverse(b.begin(), b.end());
	ar<int, 3> tt = solve(a, b);
	tt[2] = (int)b.size() - tt[2] - tt[0];
	//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
	//~ cout<<tt[0]<<" "<<tt[1]<<" "<<tt[2]<<"\n";
	
	res = max(res, tt);
	
	//~ assert(res[0]);
	if(!res[0]){
		cout<<0<<"\n";
		return 0;
	}
	cout<<res[0]<<"\n";
	cout<<res[1]<<" "<<res[2]<<"\n";
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 304 KB Output is correct
2 Correct 70 ms 300 KB Output is correct
3 Correct 45 ms 312 KB Output is correct
4 Correct 45 ms 212 KB Output is correct
5 Correct 57 ms 212 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 304 KB Output is correct
2 Correct 70 ms 300 KB Output is correct
3 Correct 45 ms 312 KB Output is correct
4 Correct 45 ms 212 KB Output is correct
5 Correct 57 ms 212 KB Output is correct
6 Execution timed out 1587 ms 212 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 304 KB Output is correct
2 Correct 70 ms 300 KB Output is correct
3 Correct 45 ms 312 KB Output is correct
4 Correct 45 ms 212 KB Output is correct
5 Correct 57 ms 212 KB Output is correct
6 Execution timed out 1587 ms 212 KB Time limit exceeded
7 Halted 0 ms 0 KB -