oj.uz

Submission #547027

# Submission time Handle Problem Language Result Execution time Memory
547027 2022-04-09T08:47:47 Z ngrace Copy and Paste 3 (JOI22_copypaste3) C++14
0 / 100
 3000 ms 522092 KB 
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <string>
using namespace std;
#define v vector
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
 
int main(){
    int N;
    cin>>N;
    string S;
    cin>>S;
    ll A,B,C;
    cin>>A>>B>>C;
 
    map<string, int> subToInd;
    map<pii, int> pairToInd;
    v<set<int>> indToStarts(N*N+100);
    int subInd=1;
    for(int l=0; l<N; l++){
        string sub="";
        for(int r=l; r<N; r++){
            sub.push_back(S[r]);
            int ind=subToInd[sub];
            if(ind==0){
                subToInd[sub]=subInd++;
                ind=subInd;
            }
            pairToInd[{l,r-l+1}] = ind;
            indToStarts[ind].insert(l);
        }
    }
 
    v<v<int>> nextOccur(N,v<int>(N+1,N));
    for(int i=N-1; i>=0; i--){
        for(int s=1; s<=N-i; s++){
            int ind=pairToInd[{i,s}];
            auto next = indToStarts[ind].lower_bound(i+s);
            if(next!=indToStarts[ind].end()) nextOccur[i][s]=(*next);
        }
    }
 
    
    v<v<ll>> dp(N, v<ll>(N,1e17));
    for(int s=1; s<=N; s++){
        for(int l=N-1; l>=0; l--){
            dp[l][l]=A;
            if(s!=1 && l+s-1<N){
                dp[l][l+s-1] = min(dp[l][l+s-1], A+dp[l+1][l+s-1]);
                dp[l][l+s-1] = min(dp[l][l+s-1], dp[l][l+s-1-1]+A);
            }
            int num=2, nex=nextOccur[l][s];
            while(nex<N){
                int r=nex+s-1;
                dp[l][r] = min(dp[l][r], dp[l][l+s-1]+B+C*num+(r-l+1 - num*s)*A);
                dp[l][r] = min(dp[l][r], A+dp[l+1][r]);
                dp[l][r] = min(dp[l][r], dp[l][r-1]+A);
                nex=nextOccur[nex][s];
                num++;
            }
        }
    }
 
    cout<<dp[0][N-1]<<endl;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2220 ms 381776 KB Output is correct
4 Correct 2674 ms 446412 KB Output is correct
5 Execution timed out 3090 ms 522092 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -