Submission #916468

#	Time	Username	Problem	Language	Result	Execution time	Memory
916468		GusterGoose27	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	577 ms	112304 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2505;
int n;
int arr[MAXN];
int match[MAXN][MAXN];
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
int a, b, c;
vvi substrings[MAXN]; // at each length, equiv classes at that length
int max_account[MAXN];
ll dp[MAXN][MAXN];
int nxt[MAXN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string s; cin >> n >> s >> a >> b >> c;
	for (int i = 0; i < n; i++) arr[i] = s[i]-'a';
	for (int i = n-1; i >= 0; i--) {
		for (int j = i-1; j >= 0; j--) {
			match[i][j] = match[j][i] = (arr[i] == arr[j] ? 1+match[i+1][j+1] : 0);
		}
	}
	for (int i = 0; i < n; i++) {
		vvi cur_matches(n+1, vi({i}));
		for (int j = i+1; j < n; j++) {
			for (int v = max_account[i]+1; v <= match[i][j]; v++)
				cur_matches[v].push_back(j);
			max_account[j] = max(max_account[j], match[i][j]);
		}
		for (int v = 0; v <= n; v++) {
			if (cur_matches[v].size() > 1) {
				sort(cur_matches[v].begin(), cur_matches[v].end());
				substrings[v].push_back(cur_matches[v]);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) dp[i][j] = (ll)a*(j-i+1);
	}
	for (int v = 1; v <= n; v++) {
		for (vector<int> p: substrings[v]) {
			ll cur_cost = dp[p[0]][p[0]+v-1]+b;
			int j = p.size();
			for (int i = p.size()-1; i >= 0; i--) {
				while (j && p[j-1] >= p[i]+v) j--;
				nxt[i] = j;
				int e = i;
				int num = 1;
				while (e < p.size()) {
					int l = p[i], r = p[e]+v-1;
					dp[l][r] = min(dp[l][r], (ll)a*(r-l+1-num*v) + cur_cost + (ll)c*num);
					num++;
					e = nxt[e];
				}
			}
		}
		// add expansion
		for (int i = 0; i < n; i++) {
			int j = i+v-1;
			if (j >= n) continue;
			if (j < n-1) dp[i][j+1] = min(dp[i][j+1], dp[i][j]+a);
			if (i) dp[i-1][j] = min(dp[i-1][j], dp[i][j]+a);
		}
	}
	cout << dp[0][n-1] << '\n';
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     while (e < p.size()) {
      |            ~~^~~~~~~~~~

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