Submission #592449

#	Time	Username	Problem	Language	Result	Execution time	Memory
592449		79brue	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	683 ms	82932 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000000039LL;

int n;
ll A, B, C;
char str[2502];
int arr[2502];
ll hashVal[2502][2502];
ll DP[2502][2502];
int nxt[2502];

int main(){
    scanf("%d %s %lld %lld %lld", &n, str+1, &A, &B, &C);
    for(int i=1; i<=n; i++) arr[i] = str[i] - 'a';
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            hashVal[i][j] = (hashVal[i][j-1] * 1000003 + arr[j]) % MOD;
        }
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) DP[i][j] = 1e18;
    for(int i=1; i<=n; i++) DP[i][i] = A;

    for(int d=0; d<n; d++){
        map<ll, int> mp;
        for(int i=1; i+d<=n; i++){
            int j = i+d;
            DP[i][j] = min({DP[i][j], DP[i+1][j]+A, DP[i][j-1]+A});
        }
        for(int i=n-d; i>=1; i--){
            int j = i+d;
            if(mp[hashVal[i][j]]) nxt[i] = mp[hashVal[i][j]];
            else nxt[i] = 0;
            if(j+d<=n) mp[hashVal[j][j+d]] = j;
        }
        for(int i=1; i+d<=n; i++){
            int e = i+d;
            int cnt = 1;
            while(nxt[e-d]){
                e = nxt[e-d]+d;
                cnt++;
//                printf("Set %d %d to %lld\n", i, e, DP[i][i+d] + B + C * cnt + A * (e-i+1 - cnt*(d+1)));
                DP[i][e] = min(DP[i][e], DP[i][i+d] + B + C * cnt + A * (e-i+1 - cnt*(d+1)));
            }
//            printf("%d %d: %lld\n", i, i+d, DP[i][i+d]);
        }
    }

    printf("%lld", DP[1][n]);
}

Compilation message (stderr)

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