oj.uz

답안 #303063

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
303063 2020-09-19T20:28:38 Z bigg Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 1 ms 1152 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3010;
int dpsufsuf[MAXN][MAXN], dpprefsuf[MAXN][MAXN];
string a, b;
int ans, ians, jans;
void fazdp(int isrev){
	int t1 = a.length();
	int t2 = b.length();
	t1--;
	t2--;
	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];
			}
		}
	}
	for(int i = t1; i ; i--){
		for(int j = t2; j; j--){
			if(a[i] == b[j]){
				dpprefsuf[i + dpsufsuf[i][j] - 1][j] = max(dpprefsuf[i + dpsufsuf[i][j] - 1][j], dpsufsuf[i][j]);
			}
		}
	}
	for(int i = 1; i <= t1; i++){
		for(int j = 1; j <= t2; j++){
			if(dpsufsuf[i][j] + dpprefsuf[i-1][dpsufsuf[i][j] + j] > ans){
				if(!isrev) jans = j;
				else{
					jans = t2 - (j + dpsufsuf[i][j] + dpprefsuf[i-1][dpsufsuf[i][j] + j] - 1) + 1;
				}
				ians = i - dpprefsuf[i-1][j + dpsufsuf[i][j]];
				ans = dpsufsuf[i][j] + dpprefsuf[i-1][dpsufsuf[i][j] + j];
			}
		}
	}
}

int main(){
	cin >> a;
	a = '0' + a;
	cin >> b;
	b = '0' + b;
	fazdp(0);
	reverse(b.begin(), b.end());
	fazdp(1);
	cout << ans << endl;
	cout << ians << ' ' << jans << endl;
}

Subtask #1
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -