oj.uz

Submission #642594

# Submission time Handle Problem Language Result Execution time Memory
642594 2022-09-20T07:47:35 Z aebov Necklace (Subtask 1-3) (BOI19_necklace1) C++17
25 / 85
 1500 ms 304 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<utility>
#define pii pair<int, int>
#define F first
#define S second
#define ll long long
#define pb push_back
using namespace std;

int n ,m ;
string s ,t;

pair<int,pii> ans(string a, string b){
	pair<int , pii > ret; n = a.size(), m = b.size();

	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 s2 = string(a.begin() + i - k, a.begin() + i);
				string t2 = string(b.begin() + j, b.begin() + j + k);
				if(s2 == t2)mx = k;
			}

			for(int k = 0 ; k <= min (j, n - i); k ++){
				string s2 = string(a.begin() + i, a.begin() + i + k);
				string t2 = string(b.begin() + j - k, b.begin() + j);
				if(s2 == t2){
					ret = max(ret, {mx + k,{ i - mx, j - k } });
				}
			}
		}
	}
	return ret;
}
int main(){
	cin >> s >> t;

	auto ret = ans(s, t);
	reverse(t.begin(), t.end());
	auto ter = ans(s, t);
	ter.S.S = (int)t.size() - ter.S.S - ter.F;

	ret = max(ret, ter);

	if(!ret.F){
		cout << 0 << endl;
		return 0;
	}
	cout << ret.F << endl << ret.S.F << " " << ret.S.S << endl; 

}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 292 KB Output is correct
2 Correct 68 ms 212 KB Output is correct
3 Correct 40 ms 284 KB Output is correct
4 Correct 43 ms 212 KB Output is correct
5 Correct 58 ms 280 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 292 KB Output is correct
2 Correct 68 ms 212 KB Output is correct
3 Correct 40 ms 284 KB Output is correct
4 Correct 43 ms 212 KB Output is correct
5 Correct 58 ms 280 KB Output is correct
6 Execution timed out 1584 ms 304 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 292 KB Output is correct
2 Correct 68 ms 212 KB Output is correct
3 Correct 40 ms 284 KB Output is correct
4 Correct 43 ms 212 KB Output is correct
5 Correct 58 ms 280 KB Output is correct
6 Execution timed out 1584 ms 304 KB Time limit exceeded
7 Halted 0 ms 0 KB -