제출 #526474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526474		ali22413836	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	0 / 85	40 ms	105932 KiB

necklace

#include <bits/stdc++.h>
#define endl "\n"
typedef long long ll ;
using namespace std;

string S, T ;
int N , M , dp1[3001][3001] , dp2[3001][3001] , lcs[3001][3001] , ans , ind , ind2 ;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> S >> T;
    int N = S.size();
    int M = T.size();
    for (int s = 0; s < N; s++){
        for (int t = 0; t < M; t++){
            lcs[s][t] = S[s] == T[t] ? ((s > 0 && t > 0 ? lcs[s - 1][t - 1] : 0) + 1) : 0;
        }
    }
    for (int s = 0; s < N; s++){
        for (int t = 0; t < M; t++){
            if (lcs[s][t] > 0){
                dp1[s][t - lcs[s][t] + 1] = max(dp1[s][t - lcs[s][t] + 1], lcs[s][t]);
                dp2[s - lcs[s][t] + 1][t] = max(dp2[s - lcs[s][t] + 1][t], lcs[s][t]);
            }
        }
    }
    for (int s = 0; s < N; s++){
        for (int t = 0; t < M; t++){
            if (t > 0) dp1[s][t] = max(dp1[s][t], dp1[s][t - 1] - 1);
            if (s > 0) dp2[s][t] = max(dp2[s][t], dp2[s - 1][t] - 1);
        }
    }
    for (int s = 0; s < N; s++){
        for (int t = 0; t < M; t++){
            int k = dp1[s][t] + (s + 1 < N && t > 0 ? dp2[s + 1][t - 1] : 0);
            if (k > 0){
                if(k > ans){
                    ans = k  ;
                    ind = s - dp1[s][t] + 1 ;
                    ind2 = t + dp1[s][t] - k ;
                }
            }
        }
    }
    for(int i = 0 ; i < 3000 ; i++){
        for(int j = 0 ; j < 3000; j++){
            dp1[i][j] = dp2[i][j] = lcs[i][j] = 0 ;
        }
    }
    reverse(begin(T), end(T));
    for (int s = 0; s < N; s++){
        for (int t = 0; t < M; t++){
            lcs[s][t] = S[s] == T[t] ? ((s > 0 && t > 0 ? lcs[s - 1][t - 1] : 0) + 1) : 0;
        }
    }
    for (int s = 0; s < N; s++){
        for (int t = 0; t < M; t++){
            if (lcs[s][t] > 0){
                dp1[s][t - lcs[s][t] + 1] = max(dp1[s][t - lcs[s][t] + 1], lcs[s][t]);
                dp2[s - lcs[s][t] + 1][t] = max(dp2[s - lcs[s][t] + 1][t], lcs[s][t]);
            }
        }
    }
    for (int s = 0; s < N; s++){
        for (int t = 0; t < M; t++){
            if (t > 0) dp1[s][t] = max(dp1[s][t], dp1[s][t - 1] - 1);
            if (s > 0) dp2[s][t] = max(dp2[s][t], dp2[s - 1][t] - 1);
        }
    }
    for (int s = 0; s < N; s++){
        for (int t = 0; t < M; t++){
            int k = dp1[s][t] + (s + 1 < N && t > 0 ? dp2[s + 1][t - 1] : 0);
            if (k > 0){
                if(k > ans){

                    ans = k  ;
                    ind = s - dp1[s][t] + 1 ;
                    ind2 = (t + dp1[s][t] - k) ;
                }
            }
        }
    }
    cout << ans << " " << ind << " " << ind2 << endl  ;
    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40