Submission #568036

#	Time	Username	Problem	Language	Result	Execution time	Memory
568036		dantoh000	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	879 ms	127916 KiB

copypaste3

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> ii;
const int INF = 1000000000000000000;
int n;
string s;
int a,b,c;
int dp[4505][4505];
int hsh[4505][4505];
int hsh2[4505][4505];
int nxt[4505][4505];
int mod = 1000000007, mod2 = 1000000009;
int H = 29, H2 = 31;
map<ii, 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] = hsh2[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;
            hsh2[i][j] = (hsh2[i][j-1]*H2 + (s[j-1]-'a'+1))%mod2;
        }
    }

    for (int i = 1; i <= n/2; i++){
        groups.clear();
        for (int j = 0; j+i <= n; j++){
            groups[{hsh[j][j+i], hsh2[j][j+1]}].push_back(j);
        }
        for (auto it : groups){
            auto V = it.second;
            int cur = 0;
            for (int k = 0; k < V.size(); k++){
                int j = V[k];
                while (cur < V.size() && V[cur] < j+i) cur++;
                ///printf("%d, length %d --> %d\n",j,i,cur);
                if (cur == V.size()) nxt[i][j] = -1;
                else nxt[i][j] = V[cur];
            }
        }


    }

    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){
            for (int j = 0; j+i <= n; j++){
                int 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);
                    cur = nxt[i][cur];
                    if (cur == -1) break;
                }
            }
        }

    }

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

Compilation message (stderr)

copypaste3.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:37:31: 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]
   37 |             for (int k = 0; k < V.size(); k++){
      |                             ~~^~~~~~~~~~
copypaste3.cpp:39:28: 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]
   39 |                 while (cur < V.size() && V[cur] < j+i) cur++;
      |                        ~~~~^~~~~~~~~~
copypaste3.cpp:41:25: 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]
   41 |                 if (cur == V.size()) nxt[i][j] = -1;
      |                     ~~~~^~~~~~~~~~~
copypaste3.cpp:62:21: warning: unused variable 'idx' [-Wunused-variable]
   62 |                 int idx = 0;
      |                     ^~~
copypaste3.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
copypaste3.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%lld%lld%lld",&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