Submission #548714

#	Time	Username	Problem	Language	Result	Execution time	Memory
548714		Ronin13	Copy and Paste 3 (JOI22_copypaste3)	C++14	57 / 100	3079 ms	33748 KiB

copypaste3

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int NMAX = 2501 + 1;
const int inf = 1e9 + 1;
const ll linf = 1e18 + 1;


ll h[NMAX];
const ll mod = 1e9 + 7;
const ll pr = 29;
ll po[NMAX];
string s;

void fil(){
    int n = s.size();
    h[0] = 0;
    for(int i = 1; i <= n; i++){
        ll x = s[i - 1] - 'a';
        h[i] = h[i - 1] * 29 + x;
        h[i] %= mod;
    }
}

ll gethash(int l, int r){
    ll x = h[r] - h[l - 1] * po[r - l + 1];
    x %= mod;
    x += mod;
    x %= mod;
    return x;
}

ll cnt[2501][2501];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    po[0] = 1;
    for(int i = 1; i <= 2500; i++){
        po[i] = po[i - 1] * pr;
        po[i] %= mod;
    }
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cnt[i][j] = linf;
        }
    }
    cin >> s;
    ll a, b, c; cin >> a >> b >> c;
    fil();
    for(int r = 1; r <= n; r++){
        pii dp[n + 1];
        for(int i = 1; i <= n;  i++){
            dp[i] = {inf, 0};
        }
        dp[1] = {r, 1};
        cnt[r][r] = a;
        for(int l = r - 1; l >= 1; l--){
            for(int sz = 1; sz <= r - l + 1; sz++){
                ll x = gethash(l, l + sz - 1);
                ll y = gethash(r - sz + 1, r);
                if(x == y){
                    if(dp[sz].f > l + sz - 1){
                        dp[sz].s++;
                        dp[sz].f = l;
                    }
                }
            }
            cnt[l][r] = cnt[l][r - 1] + a;
            for(int sz = 1; sz <= r - l + 1; sz++){
                ll m = dp[sz].s;
                ll val = cnt[r - sz + 1][r];
                cnt[l][r] = min(cnt[l][r], (c - sz * a) * m + (r - l + 1) * a + val + b);
            }
        }

    }
    /*for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(cnt[i][j] == linf)cout << - 1 << " ";
            else cout << cnt[i][j] << " ";
        }
        cout << "\n";
    }*/
    cout << cnt[1][n];
    return 0;
}

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