oj.uz

Submission #303070

# Submission time Handle Problem Language Result Execution time Memory
303070 2020-09-19T20:49:15 Z bigg Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 210 ms 71292 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3010;
int dpsufsuf[MAXN][MAXN], dpprefsuf[MAXN][MAXN];
char a[MAXN], b[MAXN];
int ans, ians, jans;
void fazdp(int isrev){
	int t1 = strlen(a + 1);
	int t2 = strlen(b + 1);
	
	for(int i = t1; i; i--){
		for(int j = t2; j; j--){
			if(a[i] == b[j]){
				dpsufsuf[i][j] = 1 + dpsufsuf[i+1][j+1];
				dpprefsuf[i + dpsufsuf[i][j] - 1][j] = max(dpprefsuf[i + dpsufsuf[i][j] - 1][j], dpsufsuf[i][j]);
	
			}
		}
	}
	// for(int i = t1; i ; i--){
	// 	for(int j = t2; j; j--){
	// 		if(a[i] == b[j]){
	// 				}
	// 	}
	// }
	for(int i = 1; i <= t1; i++){
		for(int j = 1; j <= t2; j++){
			int v = dpsufsuf[i][j] + dpprefsuf[i-1][dpsufsuf[i][j] + j];
			if( v > ans){
				if(!isrev) jans = j;
				else{
					int aux = j + v -1;
					jans = t2 - aux + 1;
				}
				ians = i - dpprefsuf[i-1][j + dpsufsuf[i][j]];
				ans = v;
			}
		}
	}
}

int main(){
	cin >>( a + 1);
	//a = '0' + a;
	cin >> (b + 1);
	//b = '0' + b;
	fazdp(0);
	int st = strlen(b + 1);
	//cout << b +1;
	for(int i = 1, j = st; i < j; i++, j--){
		swap(b[i], b[j]);

	}
	memset(dpsufsuf, 0 , sizeof(dpsufsuf));
	memset(dpprefsuf, 0 , sizeof(dpprefsuf));
	//cout << b + 1;	
	fazdp(1);
	cout << ans << endl;
	cout << ians -1<< ' ' << jans -1 << endl;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 71288 KB Output is correct
2 Correct 42 ms 71288 KB Output is correct
3 Correct 42 ms 71288 KB Output is correct
4 Correct 41 ms 71244 KB Output is correct
5 Correct 42 ms 71288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 71288 KB Output is correct
2 Correct 42 ms 71288 KB Output is correct
3 Correct 42 ms 71288 KB Output is correct
4 Correct 41 ms 71244 KB Output is correct
5 Correct 42 ms 71288 KB Output is correct
6 Correct 45 ms 71288 KB Output is correct
7 Correct 44 ms 71288 KB Output is correct
8 Correct 45 ms 71288 KB Output is correct
9 Correct 44 ms 71288 KB Output is correct
10 Correct 44 ms 71292 KB Output is correct
11 Correct 43 ms 71272 KB Output is correct
12 Correct 45 ms 71288 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 71288 KB Output is correct
2 Correct 42 ms 71288 KB Output is correct
3 Correct 42 ms 71288 KB Output is correct
4 Correct 41 ms 71244 KB Output is correct
5 Correct 42 ms 71288 KB Output is correct
6 Correct 45 ms 71288 KB Output is correct
7 Correct 44 ms 71288 KB Output is correct
8 Correct 45 ms 71288 KB Output is correct
9 Correct 44 ms 71288 KB Output is correct
10 Correct 44 ms 71292 KB Output is correct
11 Correct 43 ms 71272 KB Output is correct
12 Correct 45 ms 71288 KB Output is correct
13 Correct 203 ms 71288 KB Output is correct
14 Correct 147 ms 71288 KB Output is correct
15 Correct 210 ms 71288 KB Output is correct
16 Correct 145 ms 71288 KB Output is correct
17 Correct 112 ms 71288 KB Output is correct
18 Correct 118 ms 71288 KB Output is correct
19 Correct 153 ms 71288 KB Output is correct
20 Correct 182 ms 71288 KB Output is correct
21 Correct 189 ms 71288 KB Output is correct