oj.uz

답안 #303069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
303069 2020-09-19T20:48:55 Z bigg Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 42 ms 71288 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
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 71288 KB Expected integer, but "umnyllllllllllllllllllllllllll...lllllllllllllllllllllazksilfg84" found
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 71288 KB Expected integer, but "umnyllllllllllllllllllllllllll...lllllllllllllllllllllazksilfg84" found
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 71288 KB Expected integer, but "umnyllllllllllllllllllllllllll...lllllllllllllllllllllazksilfg84" found
2 Halted 0 ms 0 KB -