Submission #1036434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036434		aymanrs	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	559 ms	348868 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;
vector<int> z_func(const string& s){
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for(int i = 1;i < n;i++){
        if(i<r) z[i] = min(z[i-l], r-i);
        if(z[i]+i>=r){
            while(z[i]+i<n && s[z[i]+i] == s[z[i]]) z[i]++;
            r = z[i]+i;
            l = i;
        }
    }
    return z;
}
struct up {
    int i, j, c;
};
void solve(){
    int n;long long a,b,C;string s;
    cin >> n >> s >> a >> b >> C;
    long long dp[n+1][n+1];
    int nxr[n][n];
    vector<int> Z[n];
    long long L[n] = {0};
    vector<up> upd[n];
    for(int i = n-1;i >= 0;i--){
        Z[i] = z_func(s.substr(i));
        nxr[i][i]=find(s.begin()+i+1, s.end(), s[i])-s.begin();
        for(int j = i+1;j < n;j++){
            nxr[i][j] = nxr[i][j-1];
            while(nxr[i][j] < n && (nxr[i][j]<=j || Z[i][nxr[i][j]-i] < (j-i+1))) nxr[i][j]++;
        }
        for(int j = i;j < n;j++){
            if(nxr[i][j] >= n) break;
            int cj = nxr[i][j];up u = {i,j,1};
            while(cj<n){
                u.c++;
                upd[cj+j-i].push_back(u);
                cj = nxr[cj][cj+j-i];
            }
        }
    }
    for(int R = 0;R < n;R++){
        for(auto [i,j,c] : upd[R]){
            L[i] = max(L[i], -dp[i][j]-b+(a*(j-i+1)-C)*c);
        }
        for(int i = R-1;i >= 0;i--) L[i] = max(L[i], L[i+1]);
        for(int i = 0;i <= R;i++) dp[i][R] = a*(R-i+1)-L[i];
    }
    cout << dp[0][n-1] << '\n';;
}   
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 38 / 38