Submission #625284

#	Time	Username	Problem	Language	Result	Execution time	Memory
625284		flappybird	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	1108 ms	49840 KiB

copypaste3

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 2510
#define MAXS 20
#define INF 1000000000000000001
#define MOD 998244353
#define bb ' '
#define ln '\n'
#define Ln '\n'
ll dp[MAX][MAX];
#define base 1557
ll mpow[MAX];
ll hv[MAX];
int nxt[MAX];
#define hf(x) ((x)-'a'+1)
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	string s;
	cin >> s;
	ll A, B, C;
	cin >> A >> B >> C;
	int k, i, j;
	mpow[0] = 1;
	for (i = 0; i < N; i++) for (j = 0; j < N; j++) dp[i][j] = INF;
	for (i = 1; i <= N; i++) mpow[i] = 1ll * mpow[i - 1] * base, mpow[i] %= MOD;
	for (i = 0; i < N; i++) dp[i][i] = A;
	for (k = 1; k <= N; k++) {
		ll hash = 0;
		for (i = 0; i < k; i++) hash *= base, hash += hf(s[i]), hash %= MOD;
		map<ll, vector<int>> vall;
		if (k > 1) {
			for (i = 0; i < (N - k + 1); i++) {
				int j = i + k - 1;
				dp[i][j] = min(dp[i][j], min(dp[i + 1][j], dp[i][j - 1]) + A);
			}
		}
		for (i = 0; i < (N - k + 1); i++) {
			vall[hash].push_back(i);
			hv[i] = hash;
			hash *= base;
			if (i + k < N) hash += hf(s[i + k]);
			hash -= 1ll * mpow[k] * hf(s[i]);
			hash %= MOD;
			while (hash < 0) hash += MOD;
		}
		for (auto it = vall.begin(); it != vall.end(); it++) {
			ll h = it->first;
			int M = vall[h].size();
			int e = 0;
			for (int p = 0; p < M; p++) {
				while (e < M && vall[h][e] < vall[h][p] + k) e++;
				if (e >= M) nxt[vall[h][p]] = 0;
				else nxt[vall[h][p]] = vall[h][e];
			}
		}
		for (i = 0; i < (N - k + 1); i++) {
			if (!nxt[i]) continue;
			int r = nxt[i] + k - 1;
			int j = i + k - 1;
			int cnt = 2;
			while (1) {
				dp[i][r] = min(dp[i][r], dp[i][j] + B + C * cnt + A * ((ll)r - i + 1 - (ll)cnt * ((ll)j - i + 1)));
				if (!nxt[r - k + 1]) break;
				r = nxt[r - k + 1] + k - 1;
				cnt++;
			}
		}
	}
	cout << dp[0][N - 1] << ln;
}

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