Submission #799567

#	Time	Username	Problem	Language	Result	Execution time	Memory
799567		eltu0815	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	1636 ms	225280 KiB

copypaste3

#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
 
int n, m, k, q, l, tt;
int h[2505][2505];
ll dp[2505][2505];
int prv[6250005];
string str;
unordered_map<ll, int> mp[2505];
int nxt[2505][2505];
char inp[2505];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int idx = 0;
    cin >> n >> str;
    ll a, b, c; cin >> a >> b >> c;
    for(int i = 1; i <= n; ++i) {
        ll sum1 = 0, sum2 = 0;
        for(int j = i, t = 1, t2 = 1; j <= n; ++j, t = t * 37ll % MOD, t2 = t2 * 31ll % MOD) {
            sum1 = (sum1 + ((ll)str[j - 1] - 'a' + 1) * t % MOD) % MOD;
            sum2 = (sum2 + ((ll)str[j - 1] - 'a' + 1) * t2 % MOD) % MOD;
            if(!mp[j - i + 1][sum1 * MOD + sum2]) mp[j - i + 1][sum1 * MOD + sum2] = ++idx;
            h[i][j] = mp[j - i + 1][sum1 * MOD + sum2];
            
        }
    }
    
    for(int j = n; j >= 1; --j) {
        for(int i = j; i >= 1; --i) if(prv[h[i][j]]) nxt[i][j] = prv[h[i][j]];
        for(int k = j; k <= n; ++k) prv[h[j][k]] = j;
    }
    
    
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) dp[i][j] = INF;
    for(int l = 0; l <= n - 1; ++l) for(int i = 1; i <= n - l; ++i) {
        int j = i + l, cnt = 1, x = i;
        if(i == j) dp[i][j] = a;
        else dp[i][j] = min(dp[i][j], min(dp[i][j - 1] + a, dp[i + 1][j] + a));
        
        int l = j - i + 1;
        while(true) {
            ++cnt; x = nxt[x][x + l - 1];
            if(x == 0) break;
            dp[i][x + l - 1] = min(dp[i][x + l - 1], dp[i][j] + b + (ll)cnt * c + (x + l - i - (ll)l * cnt) * a);
        }
    }
    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