Submission #1205947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205947		siewjh	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	2747 ms	822604 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2505;
const int MAXND = 4000000;
vector<pair<char, int>> adj[MAXND];
vector<int> stn[MAXND];
vector<tuple<int, int, int>> seqv[MAXN][MAXN];
ll A, B, C, memo[MAXN][MAXN];
void dfs(int x, int d){
	int sz = stn[x].size();
	vector<int> nxt(sz);
	for (int i = 0; i < sz; i++) nxt[i] = lower_bound(stn[x].begin(), stn[x].end(), stn[x][i] + d) - stn[x].begin();
	for (int i = 0; i < sz; i++){
		int l = stn[x][i];
		for (int curr = nxt[i], occ = 2; curr < sz; curr = nxt[curr], occ++) seqv[l][stn[x][curr] + d - 1].push_back({l, l + d - 1, occ});
	}
	for (auto [nc, nn] : adj[x]) dfs(nn, d + 1);
}
ll dp(int l, int r){
	if (l == r) return A;
	if (memo[l][r] != -1) return memo[l][r];
	ll ans = min(dp(l + 1, r), dp(l, r - 1)) + A;
	for (auto [ls, rs, occ] : seqv[l][r]){
		int len = rs - ls + 1, rem = r - l + 1 - occ * len;
		ans = min(ans, dp(ls, rs) + B + occ * C + rem * A);
	}
	return memo[l][r] = ans;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int nums; cin >> nums;
	string str; cin >> str;
	int ind = 0;
	for (int i = 0; i < nums; i++){
		int x = 0;
		for (int j = i; j < nums; j++){
			bool flag = 0;
			for (auto [nc, nn] : adj[x])
				if (nc == str[j]){
					x = nn; flag = 1;
				}
			if (!flag){
				adj[x].push_back({str[j], ++ind});
				x = ind;
			}
			stn[x].push_back(i);
		}
	}
	dfs(0, 0);
	cin >> A >> B >> C;
	memset(memo, -1, sizeof(memo));
	cout << dp(0, nums - 1);
}

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