Submission #703065

#	Time	Username	Problem	Language	Result	Execution time	Memory
703065		ajpiano	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	769 ms	49484 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

const int tests = 0;

#define f first
#define s second

typedef long long ll;
typedef pair<ll,ll> pi;

const ll mod1 = 1e9+7;
const ll mod2 = 1e9+9;
ll mult = 29;

ll binexp1(ll num, ll p){
    if(p == 0) return 1;
    if(p == 1) return num;
    ll ans = binexp1(num, p/2LL);
    ans = ans*ans%mod1;
    if(p&1) ans = ans*num%mod1;
    return ans;
}

ll binexp2(ll num, ll p){
    if(p == 0) return 1;
    if(p == 1) return num;
    ll ans = binexp2(num, p/2LL);
    ans = ans*ans%mod2;
    if(p&1) ans = ans*num%mod2;
    return ans;
}

struct hashnum{
    int sz = 0;
    ll num = 0;
    ll num1 = 0, num2 = 0;
    void add(char a){
        num1 *= mult; num1 += (a-'a'+1);
        num1 %= mod1;
        num2 *= mult; num2 += (a-'a'+1);
        num2 %= mod2;
        
        sz++;

        num = num2*mod2 + num1;
    }
    void rem(char a){
        num1 -= binexp1(mult, sz-1)*(ll)(a-'a'+1);
        num1 %= mod1;
        if(num1 < 0) num1 += mod1;

        num2 -= binexp2(mult, sz-1)*(ll)(a-'a'+1);
        num2 %= mod2;
        if(num2 < 0) num2 += mod2;

        sz--;

        num = num2*mod2 + num1;
    }
};

void solve(){
    int n; cin >> n;
    string s; cin >> s;
    ll a,b,c; cin >> a >> b >> c;

    ll dp[n+1][n+1];
    //set up array
    for(int i = 1; i <= n; i++){
        for(int j = 1; j+i-1 <= n; j++){
            dp[i][j] = a*(ll)(i);
        }
    }

    //do dp
    for(int sz = 1; sz <= n; sz++){
        hashnum curhash;
        vector<int> next(n+1, n+1);
        vector<ll> shash(n+1);
        map<ll, int> last; 
        for(int i = 1; i <= sz; i++) curhash.add(s[i-1]);
        for(int l = 1; l+sz-1 <= n; l++){
            if(sz != 1){
                dp[sz][l] = min(dp[sz][l], a+min(dp[sz-1][l], dp[sz-1][l+1]));
            }
            //go through
            if(l > 1){
                curhash.rem(s[l-2]);
                curhash.add(s[l+sz-2]);
            }
            //assign this substring hash
            shash[l] = curhash.num;

            //add the newly valid hash to the map
            if(l-sz > 0){
                last[shash[l-sz]] = l-sz;
            }
            auto it = last.find(shash[l]);
            if(it != last.end()){
                next[it->s] = l;
            }
        }
        for(int l = 1; l <= n; l++){
            int r = next[l];
            for(ll i = 2; r <= n; i++){
                //cost = letter cost + pastes + cut + creation - extra letter count
                dp[r-l+sz][l] = min(dp[r-l+sz][l], a*(ll)(r-l - (i-1)*sz) + c*i + b + dp[sz][l]);
                r = next[r];
            }
        }
    }

    cout << dp[n][1] << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    if(tests) cin >> t;
    while(t--) solve();
}

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