oj.uz

Submission #422874

# Submission time Handle Problem Language Result Execution time Memory
422874 2021-06-10T13:25:19 Z abdzag Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 409 ms 71184 KB 
#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 1e15;

int main() {
	cin.sync_with_stdio(false);
	string a, b;
	cin >> a >> b;
	ll ans = 0;
	ll pos1, pos2;
	vector<vector<ll>> v(3001, vector<ll>(3001));
	rep(i, 0, b.size()) {
		ll counter = 0;
		rep(j, 1, a.size()+1) {
			if (b[i+counter] == a[j-1])v[i][j] = ++counter;
			else {
				while (b[i + counter] != a[j - 1] && counter)counter--;
				if (b[i + counter] == a[j - 1])v[i][j] = ++counter;
			}
		}
	}
	rep(i, 0, a.size()) {
		ll counter = 0;
		rep(j, 1, b.size() + 1) {
			if (a[i + counter] == b[j-1])counter++;
			else {
				while (a[i + counter] != b[j - 1] && counter)counter--;
				if (a[i + counter] == b[j - 1])++counter;
			}
			if (ans < counter + v[j][i]) {
				ans = counter + v[j][i];
				pos1 = i - v[j][i];
				pos2 = j - counter;
			}
		}
	}
	reverse(all(a));
	v.clear();
	v.resize(3001, vector<ll>(3001, 0));
	rep(i, 0, b.size()) {
		ll counter = 0;
		rep(j, 1, a.size() + 1) {
			if (b[i + counter] == a[j - 1])v[i][j] = ++counter;
			else {
				while (b[i + counter] != a[j - 1]&&counter)counter--;
				if (b[i + counter] == a[j - 1])v[i][j] = ++counter;
			}
		}
	}
	rep(i, 0, a.size()) {
		ll counter = 0;
		rep(j, 1, b.size() + 1) {
			if (a[i + counter] == b[j - 1])counter++;
			else {
				while (a[i + counter] != b[j - 1] && counter)counter--;
				if (a[i + counter] == b[j - 1])counter++;
			}
			if (ans < counter + v[j][i]) {
				ans = counter + v[j][i];
				pos1 = a.size()-i - counter;
				pos2 = j - counter;
			}
		}
	}
	cout << ans << endl;
	if (ans)cout << pos1 << " " << pos2;
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 70896 KB Output is correct
2 Correct 74 ms 71044 KB Output is correct
3 Correct 77 ms 70864 KB Output is correct
4 Correct 77 ms 70996 KB Output is correct
5 Correct 90 ms 70956 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 70896 KB Output is correct
2 Correct 74 ms 71044 KB Output is correct
3 Correct 77 ms 70864 KB Output is correct
4 Correct 77 ms 70996 KB Output is correct
5 Correct 90 ms 70956 KB Output is correct
6 Correct 85 ms 71016 KB Output is correct
7 Correct 78 ms 70840 KB Output is correct
8 Correct 76 ms 70864 KB Output is correct
9 Correct 76 ms 71016 KB Output is correct
10 Correct 77 ms 70932 KB Output is correct
11 Correct 80 ms 71184 KB Output is correct
12 Correct 78 ms 71036 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 70896 KB Output is correct
2 Correct 74 ms 71044 KB Output is correct
3 Correct 77 ms 70864 KB Output is correct
4 Correct 77 ms 70996 KB Output is correct
5 Correct 90 ms 70956 KB Output is correct
6 Correct 85 ms 71016 KB Output is correct
7 Correct 78 ms 70840 KB Output is correct
8 Correct 76 ms 70864 KB Output is correct
9 Correct 76 ms 71016 KB Output is correct
10 Correct 77 ms 70932 KB Output is correct
11 Correct 80 ms 71184 KB Output is correct
12 Correct 78 ms 71036 KB Output is correct
13 Correct 373 ms 70992 KB Output is correct
14 Correct 409 ms 71000 KB Output is correct
15 Correct 374 ms 70928 KB Output is correct
16 Correct 383 ms 70940 KB Output is correct
17 Correct 357 ms 71084 KB Output is correct
18 Correct 383 ms 71128 KB Output is correct
19 Correct 386 ms 70936 KB Output is correct
20 Correct 360 ms 70988 KB Output is correct
21 Correct 403 ms 70920 KB Output is correct