Submission #710866

#	Time	Username	Problem	Language	Result	Execution time	Memory
710866		minhcool	Copy and Paste 3 (JOI22_copypaste3)	C++17	1 / 100	1055 ms	918360 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define hash hashy


typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2e3 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;

const int md1 = 1e9 + 87, md2 = 1e9 + 123;

int n, a, b, c;
string s;

int dp[N][N];

int mx[N][N];

int sparse[N][N][15];

ii hash[N];

ii pw26[N];

ii get(int l, int r){
	int temp1 = (hash[r].fi - hash[l - 1].fi * pw26[r - l + 1].fi + md1 * md1) % md1;
	int temp2 = (hash[r].se - hash[l - 1].se * pw26[r - l + 1].se + md2 * md2) % md2;
	return {temp1, temp2};
}

void process(){
    cin >> n >> s >> a >> b >> c;
	s = '*' + s;
	pw26[0] = {1, 1};
	for(int i = 1; i <= n; i++){
		hash[i].fi = (hash[i - 1].fi * 31 + s[i] - 'a') % md1;
		hash[i].se = (hash[i - 1].se * 37 + s[i] - 'a') % md2;
		pw26[i].fi = (pw26[i - 1].fi * 31) % md1;
		pw26[i].se = (pw26[i - 1].se * 37) % md2;
 	}
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(s[i] != s[j]){
				mx[i][j] = mx[j][i] = 0;
				continue;
			}
			int le = i, ri = n;
			while(le < ri){
				int mid = (le + ri + 1) >> 1;
				if((mid + (j - i)) > n) ri = mid - 1;
				ii temp1 = get(i, mid), temp2 = get(j, mid + (j - i));
				if(temp1 == temp2) le = mid;
				else ri = mid - 1;
			}
			mx[i][j] = mx[j][i] = (le - i + 1);
		//	cout << i << " " << j << " " << mx[i][j] << "\n";
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++) sparse[i][j][0] = mx[i][j];
		for(int j = 1; j <= 13; j++){
			for(int k = j; (k + (1LL << j) - 1) <= n; k++){
				sparse[i][k][j] = max(sparse[i][k][j - 1], sparse[i][k + (1LL << (j - 1))][j - 1]);
			}
		}
	}
	for(int i = 1; i <= n; i++) dp[i][i] = a;
	for(int le = n; le >= 1; le--){
		for(int ri = le + 1; ri <= n; ri++) dp[le][ri] = oo;
		for(int ri = le; ri <= n; ri++){
			dp[le][ri] = min(dp[le][ri], min(dp[le][ri - 1], dp[le + 1][ri]) + a);
			vector<int> pos;
			pos.pb(le);
			int itr = ri + 1;
			while(itr <= n){
				for(int i = 13; i >= 0; i--){
					if((itr + (1LL << i) - 1) > n) continue;
					if(sparse[le][itr][i] < (ri - le + 1)) itr += (1LL << i);
				}
				if(sparse[le][itr][0] < (ri - le + 1)) break;
				pos.pb(itr);
				itr += (ri - le + 1);
			}
			int cnt = 0;
			for(auto it : pos){
				//cout << "OK" << le << " " << ri << " " << it << "\n";
				cnt++;
				int rem = ((it + ri - le) - le + 1) - (ri - le + 1) * cnt;
				if(cnt > 1) dp[le][it + (ri - le)] = min(dp[le][it + (ri - le)], dp[le][ri] + b + c * cnt + a * rem);
			}
		}
		for(int ri = le; ri <= n; ri++){
			//cout << le << " " << ri << " " << dp[le][ri] << "\n";
		}
	}
	cout << dp[1][n] << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    //freopen("KEK.inp", "r", stdin);
    //freopen("KEK.out", "w", stdout);
    cin.tie(0);
    process();
}

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