oj.uz

Submission #526471

# Submission time Handle Problem Language Result Execution time Memory
526471 2022-02-14T21:53:00 Z ali22413836 Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 40 ms 106028 KB 
#include <bits/stdc++.h>
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 = int(T.size()) - (t + dp1[s][t] - k) - k  ;
                }
            }
        }
    }
    cout << ans << " " << ind + 1 << " " << ind2 + 1 << endl ;
    return 0;
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 106028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 106028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 106028 KB Output isn't correct
2 Halted 0 ms 0 KB -