Submission #843530

#	Time	Username	Problem	Language	Result	Execution time	Memory
843530		Cookie	Copy and Paste 3 (JOI22_copypaste3)	C++14	62 / 100	285 ms	48464 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 nxt[mxn + 1];
struct HASH{
    ll base, mod;
    ll pw[2505], hsh[2505];
    void init(string s, ll _base, ll _mod){
        base = _base; mod = _mod;
        pw[0] = 1;
        for(int i = 1; i <= n; i++){
            pw[i] = (pw[i - 1] * base) % mod;
        }
        for(int i = 1; i <= n; i++){
            hsh[i] = (hsh[i - 1] * base + (s[i - 1] - 'a' + 1)) % mod;
        }
    }
    ll gethsh(int l, int r){
        return((hsh[r] - hsh[l - 1] * pw[r - l + 1] + mod * mod) % mod);
    }
};
HASH h1, h2;
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; 
    h1.init(s, 173, rr(1e8, 1e9)); h2.init(s, 173, rr(1e8, 1e9));
    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++){
        vt<pii>comp;
        for(int j = 1; j + len - 1 <= n; j++){
            nxt[j] = -1;
            comp.pb(make_pair((h1.gethsh(j, j + len - 1) * h2.gethsh(j, j + len - 1)) % mod, j));
        }
        sort(comp.begin(), comp.end());
        
        
        for(int i = 0; i < sz(comp);){
            int r = i;
            while(r < sz(comp) && comp[r].first == comp[i].first)r++;
            int rp = i;
            for(int j = i; j < r; j++){
                while(rp < r && comp[rp].second < comp[j].second + len){
                    rp++;
                }
                if(rp == r)nxt[comp[j].second] = -1;
                else nxt[comp[j].second] = comp[rp].second;
            }
            i = r;
        }
        
        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] != -1){
                idl = nxt[idl];
                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: 0 / 38