# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
303080 | bigg | Necklace (Subtask 4) (BOI19_necklace4) | C++14 | 140 ms | 65540 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |