Submission #843550

#	Time	Username	Problem	Language	Result	Execution time	Memory
843550		Cookie	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	268 ms	72820 KiB

copypaste3

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>

const int mxn = 2505;
const ll inf = 1e18, mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rr(ll l, ll r){
    return(uniform_int_distribution<ll>(l, r)(rng));
}

ll n, a, b, c;
string s;
ll dp[mxn + 1][mxn + 1], hsh[mxn + 1], pw[mxn + 1];
int z[2505], nxt[2505][2505];
void ckmin(ll &a, ll b){
    a = min(a, b);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> a >> b >> c; 
    for(int i = 0; i < n; i++){
        int l = i, r = i;
        for(int j = i + 1; j < n; j++){
            if(j > r){
                l = r = j;
                while(r < n && s[r] == s[r - l + i])r++;
                z[j] = r - l; r--;
            }else{
                int pos = j - l + i;
                if(z[pos] < r - j + 1)z[j] = z[pos];
                else{
                    l = j;
                    while(r < n && s[r] == s[r - l + i])r++;
                    z[j] = r - l; r--;
                }
            }
        }
        int rp = i + 1;
        for(int j = 1; j <= n; j++){
            rp = max(rp, i + j);
            while(rp < n && z[rp] < j){
                rp++;
            }
            if(rp < n)nxt[i + 1][j] = rp + 1;
            else nxt[i + 1][j] = -1;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            dp[i][j] = inf;
        }
    }
    for(int len = 1; len <= n; len++){
        
        for(int i = 1; i + len - 1 <= n; i++){
            int l = i, r = i + len - 1;
            ckmin(dp[l][r], dp[l + 1][r] + a); ckmin(dp[l][r], dp[l][r - 1] + a);
            
           
            int idl = l, cnt = 1;
            while(nxt[idl][len] != -1){
                idl = nxt[idl][len];
                cnt++;
                int nwr = idl + len - 1;
                ckmin(dp[l][nwr], dp[l][r] + b + c * cnt + a * (nwr - l + 1 - len * cnt));
            }
            
        }
        
    }
    cout << dp[1][n];
    return(0);
}

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