Submission #550752

#	Time	Username	Problem	Language	Result	Execution time	Memory
550752		lkh3happy	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	1618 ms	57872 KiB

copypaste3

#include <stdio.h>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
 
char S[2501];
long long dp[2501][2501], mod=1e9+9, mod1=1300000003, h[2501], h1[2501], mul=998244353, nex[2501][2501];
 
int main(){
    h[0]=h1[0]=1;
    for(int i=1;i<2501;i++) h[i]=h[i-1]*mul%mod, h1[i]=h1[i-1]*mul%mod1;
    int n;
    long long a, b, c;
    scanf("%d%s%lld%lld%lld", &n, S, &a, &b, &c);
    for(int i=0;i<=n;i++) for(int j=i;j<=n;j++) dp[i][j]=(j-i+1)*a+b;
    for(int l=1;l<=n;l++){
        map<pair<long long, long long>, long long> m;
        queue<long long> q[2501];
        long long hc=0, hc1=0, cnt=0;
        for(int i=0;i<l;i++) hc=(hc*mul+(S[i]-'a'))%mod, hc1=(hc1*mul+(S[i]-'a'))%mod1;
        m[{hc, hc1}]=++cnt;
        q[cnt].push(0);
        for(int i=l;i<n;i++){
            hc=(hc*mul-h[l]*(S[i-l]-'a')+(S[i]-'a'))%mod;
          	hc=(hc+mod)%mod;
            hc1=(hc1*mul-h1[l]*(S[i-l]-'a')+(S[i]-'a'))%mod1;
          	hc1=(hc1+mod1)%mod1;
            if(m.find({hc, hc1})==m.end()) m[{hc, hc1}]=++cnt;
            long long x=m[{hc, hc1}];
            while(!q[x].empty() && q[x].front()+l-1<i-l+1) nex[q[x].front()][q[x].front()+l-1]=i-l-q[x].front()+1, q[x].pop();
            q[x].push(i-l+1);
        }
    }
    for(int l=1;l<=n;l++){
        for(int i=0;i<n-l+1;i++){
            int j=i+l-1, k=0, j1=j, cnt=1;
            if(i) dp[i-1][j]=min(dp[i-1][j], dp[i][j]+a);
            if(j+1!=n) dp[i][j+1]=min(dp[i][j+1], dp[i][j]+a);
            while(nex[i+k][j]){
                int x=nex[i+k][j];
                j+=x; k+=x; cnt++;
                dp[i][j]=min(dp[i][j], dp[i][j1]+(j-i+1-l*cnt)*a+b+c*cnt);
            }
        }
    }
    printf("%lld\n", dp[0][n-1]-b);
    return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d%s%lld%lld%lld", &n, S, &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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