Submission #550745

#	Time	Username	Problem	Language	Result	Execution time	Memory
550745		lkh3happy	Copy and Paste 3 (JOI22_copypaste3)	C++14	6 / 100	1177 ms	57784 KiB

copypaste3

#include <stdio.h>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

char S[2501];
long long dp[2501][2501], mod=1e9+7, h[2501], mul=101, nex[2501][2501];

int main(){
    h[0]=1;
    for(int i=1;i<2501;i++) h[i]=h[i-1]*mul%mod;
    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<long long, long long> m;
        queue<long long> q[2501];
        long long hc=0, cnt=0;
        for(int i=0;i<l;i++) hc=(hc*mul+(S[i]-'a'))%mod;
        m[hc]=++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;
            if(m.find(hc)==m.end()) m[hc]=++cnt;
            long long x=m[hc];
            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: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38