Submission #568025

#	Time	Username	Problem	Language	Result	Execution time	Memory
568025		dantoh000	Copy and Paste 3 (JOI22_copypaste3)	C++14	57 / 100	3078 ms	41300 KiB

copypaste3

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1000000000000000000;
int n;
string s;
int a,b,c;
int dp[4505][4505];
int hsh[4505][4505];
int mod = 1000000007;
int GRP[4505];
int H = 29;
map<int, vector<int> > groups;
main(){
    scanf("%lld",&n);
    cin >> s;
    scanf("%lld%lld%lld",&a,&b,&c);

    for (int i = 0; i < n; i++){
        hsh[i][i] = 0;
        for (int j = i+1; j <= n; j++){
            hsh[i][j] = (hsh[i][j-1]*H + (s[j-1]-'a'+1))%mod;
        }
    }
    for (int i = 0; i <= n; i++){
        dp[i][i] = 0;
        for (int j = i+1; j <= n; j++){
            dp[i][j] = INF;
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 0; j+i <= n; j++){
            dp[j][j+i] = min(dp[j][j+i],  min(dp[j+1][j+i], dp[j][j+i-1]) + a);
        }
        if (i <= n/2){
            groups.clear();
            for (int j = 0; j+i <= n; j++){
                GRP[j] = hsh[j][j+i];
                groups[GRP[j]].push_back(j);
            }
            for (int j = 0; j+i <= n; j++){
                int G = GRP[j];
                auto cur = j;
                int idx = 0;
                int ct = 0;
                int dpValue = dp[j][j+i];
                while (true){
                    ct++;
                    int L = j;
                    int R = cur + i;
                    dp[L][R] = min(dp[L][R], dpValue + b + ct*c + (R-L - i*ct)*a);
                    while (idx < groups[G].size() && groups[G][idx] < R) idx++;
                    if (idx == groups[G].size()) break;
                    cur = groups[G][idx];
                }
            }
        }

    }

    printf("%lld\n",dp[0][n]);
}

Compilation message (stderr)

copypaste3.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main(){
      | ^~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:52:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                     while (idx < groups[G].size() && groups[G][idx] < R) idx++;
      |                            ~~~~^~~~~~~~~~~~~~~~~~
copypaste3.cpp:53:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                     if (idx == groups[G].size()) break;
      |                         ~~~~^~~~~~~~~~~~~~~~~~~
copypaste3.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
copypaste3.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%lld%lld%lld",&a,&b,&c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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