Submission #1226549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226549		g4yuhg	Copy and Paste 3 (JOI22_copypaste3)	C++20	62 / 100	1999 ms	427416 KiB

copypaste3

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes //cout<<"YES"<<endl;
#define no //cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);//cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 2502
using namespace std;

bool ghuy4g;

const ll base = 31;
const ll mod = 1e9 + 7;

int n, A, B, C, nxt[N][N];
long long dp[2502][2502];
string s;
long long p[N], h[N];
vector<ll> vt[N][N];
unordered_map<ll, ll> mp[N];
ll cur[N];

void build() {
	p[0] = 1;
	h[0] = 0;
	for (int i = 1; i <= n; i ++) {
		h[i] = (h[i - 1] * base % mod + (s[i] - 'a')) % mod;
		p[i] = p[i - 1] * base % mod;
	}
}

ll get(ll l, ll r) {
	return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
}

void pre() {
	//vt[0][0].push_back(0);
	//ll cnt = 0;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			dp[i][j] = inf;
		}
		dp[i][i] = A;
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = i; j <= n; j ++) {
			ll x = get(i, j);
			////cout << mp[j - i + 1][x] << endl;
			//continue;
			if (mp[j - i + 1][x] == 0) {
				mp[j - i + 1][x] = ++ cur[j - i + 1];
			}
			if (j - i + 1 == 4) {
				//cout << i << " " << j << " " << mp[j - i + 1][x] << endl;
			}
			////cout << j - i + 1 << " " << mp[j - i + 1][x] << endl;
			////cout << vt[j - i + 1][mp[j - i + 1][x]].size() << endl;
			//continue;
			////cout << "size " << vt[4][1].size() << endl;
			vt[j - i + 1][mp[j - i + 1][x]].push_back(i);
		}
	}
	//exit(0);
	for (int len = 1; len <= n; len ++) {
		for (int id = 1; id <= cur[len]; id ++) {
			sort(vt[len][id].begin(), vt[len][id].end());
			ll it = vt[len][id].size() - 1;
			//cout << len << " " << id << " " << vt[len][id].size() << " " << it << endl;
			if (vt[len][id].size() == 0) continue;
			//continue;
			for (int j = vt[len][id].size() - 1; j >= 0; j --) {
				while (it > 0 && vt[len][id][it - 1] - vt[len][id][j] >= len) {
					it -- ;
				}
				if (it >= 0 && vt[len][id][it] - vt[len][id][j] >= len) {
					nxt[len][vt[len][id][j]] = vt[len][id][it];
				}
			}
		}
	}
	//cout << nxt[4][1] << endl;
	//cout << nxt[3][nxt[3][1]] << endl;
}
/*
long long dp(ll i, ll j) {
	if (i > j){
		return 0;
	}
	if (i >= j) {
		return A;
	}
	if (i < 0 || j < 0 || i > n || j > n) return inf;
	long long res = min(A + dp(i + 1, j), A + dp(i, j - 1)); // mo rong
	ll z = nxt[j - i + 1][i];
	ll cnt = 1;
	ll rc = res;
	while (z) {
		++ cnt;
		res = min(res, B + C * cnt + dp(i, z + j - i) + A * (z + j - i - i + 1 - (j - i + 1) * cnt) );
		z = nxt[j - i + 1][z];
	}
	return res;
}
*/
void solve() {
	for (int len = 1; len <= n; len ++) {
		for (int i = 1; i <= n - len + 1; i ++) {
			ll j = i + len - 1;
			dp[i][j] = min({dp[i][j], dp[i][j - 1] + A, dp[i + 1][j] + A}) ;
			ll cnt = 1, z = nxt[j - i + 1][i];
			while (z) {
				++ cnt;
				dp[i][z + len - 1] = min(dp[i][z + len - 1], dp[i][j] + B + C * cnt + (z + len - 1 - i + 1 - cnt * len) * A );
				z = nxt[j - i + 1][z];
			}
		}
	}
	cout << dp[1][n];
}

bool klinh;

signed main(void) {
    faster;
    cin >> n >> s >> A >> B >> C;
    s = '*' + s;
    build();
    pre();
    solve();
    cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
    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