Submission #1370372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370372		pirmyratg	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	325 ms	49656 KiB

copypaste3

#include "bits/stdc++.h"
using namespace std;

const int md1 = 1e9 + 7;
const int md2 = 1e9 + 9;
const int BASE = 29;

char s[505];
int main(){
    int n;
    scanf("%d", &n);
    scanf("%s", s + 1);
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    vector<int> pw1(n + 1), pw2(n + 1), h1(n + 1), h2(n + 1);
    pw1[0]=pw2[0]=1;
    for(int i = 1; i <= n; ++i){
        pw1[i]=1LL*pw1[i-1]*BASE%md1;
        pw2[i]=1LL*pw2[i-1]*BASE%md2;
        h1[i]=(1LL*h1[i-1]*BASE+(s[i]-'a'))%md1;
        h2[i]=(1LL*h2[i-1]*BASE+(s[i]-'a'))%md2;
    }
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 1e18));
    for(int len = 1; len <= n; ++len){
        vector<int> to(n + 2, -1);
        map<pair<int, int>, int> mp;
        for(int l = n - len + 1; l >= 1; --l){
            int r=l+len-1;
            if(r + len <= n){
                int v1=(h1[r+len]-1LL*h1[r]*pw1[len]%md1+md1)%md1;
                int v2=(h2[r+len]-1LL*h2[r]*pw2[len]%md2+md2)%md2;
                mp[{v1, v2}]=r+1;
            }
            int cur1=(h1[r]-1LL*h1[l-1]*pw1[len]%md1+md1)%md1;
            int cur2=(h2[r]-1LL*h2[l-1]*pw2[len]%md2+md2)%md2;
            pair<int, int> h={cur1, cur2};
            if(mp.count(h))
                to[l]=mp[h];
            if(len == 1){
                dp[l][r]=a;
            }else{
                dp[l][r]=min(dp[l][r], min(dp[l+1][r], dp[l][r-1])+a);
            }
            int x=l, cnt=1;
            while(to[x]!=-1){
                x=to[x];
                cnt++;
                int total=x+len-l;
                long long cost=dp[l][r]+b+1LL*cnt*c+1LL*(total-cnt*len)*a;
                if(cost<dp[l][x+len-1])
                    dp[l][x+len-1]=cost;
            }
        }
    }
    printf("%lld\n", dp[1][n]);
    return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
copypaste3.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%s", s + 1);
      |     ~~~~~^~~~~~~~~~~~~
copypaste3.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d%d%d", &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