제출 #625277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625277		flappybird	Copy and Paste 3 (JOI22_copypaste3)	C++17	25 / 100	3066 ms	33748 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 29
ll mpow[MAX];
ll hv[MAX];
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 += (s[i] - 'a'), hash %= MOD;
		map<ll, vector<int>> vall;
		for (i = 0; i < (N - k + 1); i++) {
			vall[hash].push_back(i);
			hv[i] = hash;
			hash *= base;
			if (i + k < N) hash += (s[i + k] - 'a');
			hash -= 1ll * mpow[k] * (s[i] - 'a');
			hash %= MOD;
			while (hash < 0) hash += MOD;
		}
		for (i = 0; i < (N - k + 1); i++) {
			j = i + k - 1;
			dp[i][j] = min(dp[i][j], min(dp[i + 1][j], dp[i][j - 1]) + A);
			ll h = hv[i];
			int M = vall[h].size();
			for (int p = 0; p < M; p++) {
				int cnt = 1;
				int l = vall[h][p];
				int pv = vall[h][p];
				for (int q = p + 1; q < M; q++) {
					if (pv + k <= vall[h][q]) cnt++, pv=vall[h][q];
					int r = vall[h][q] + k - 1;
					dp[l][r] = min(dp[l][r], dp[i][j] + B + C * cnt + A * ((ll)r - l + 1 - (ll)cnt * ((ll)j - i + 1)));
				}
			}
		}
	}
	cout << dp[0][N - 1] << ln;
}

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