Submission #874884

#	Time	Username	Problem	Language	Result	Execution time	Memory
874884		NK_	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	718 ms	253672 KiB

copypaste3

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

#define f first
#define s second
#define mp make_pair

#define sz(x) int(x.size())

using pi = pair<int, int>;
using ll = long long;

template<class T> using V = vector<T>;

using vi = V<int>;
using vl = V<ll>;
using vpi = V<pi>;
using str = string;

const int MOD = 1e9 + 7;
const ll b1 = 2003;
const ll b2 = 1009;

const ll INFL = ll(1e18);
const int LG = 18;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;
	str S; cin >> S;

	ll a, b, c; cin >> a >> b >> c;

	V<vl> dp(N, vl(N, INFL));
	V<vi> nxt(N, vi(N, -1));

	for(int l = 0; l < N; l++) for(int r = l; r < N; r++) dp[l][r] = (r - l + 1) * a;

	V<V<vi>> H(N);

	for(int w = 0; w < N; w++) {
		unordered_map<ll, int> C;
		ll h1 = 0, h2 = 0, pw1 = 1, pw2 = 1; 

		for(int l = 0; l <= w; l++) {
			h1 = (b1 * h1 + S[l]) % MOD;
			h2 = (b2 * h2 + S[l]) % MOD;
			pw1 = (pw1 * b1) % MOD;
			pw2 = (pw2 * b2) % MOD;
		}

		{
			ll h = MOD * h1 + h2;
			// cout << 0 << " " << w << " " << h << endl;
			if (C.find(h) == C.end()) C[h] = sz(H[w]), H[w].pb({});
			H[w][C[h]].pb(0);
		}

		for(int l = w + 1; l < N; l++) {
			h1 = (b1 * h1 + S[l]) % MOD;
			h2 = (b2 * h2 + S[l]) % MOD;

			h1 -= (pw1 * S[l - w - 1]) % MOD;
			h2 -= (pw2 * S[l - w - 1]) % MOD;

			if (h1 < 0) h1 += MOD;
			if (h2 < 0) h2 += MOD;


			ll h = MOD * h1 + h2;

			// cout << l << " " << w << " " << h << endl;

			if (C.find(h) == C.end()) C[h] = sz(H[w]), H[w].pb({});

			H[w][C[h]].pb(l - w);
		}
	}

	for(int w = 0; w < N; w++) {
		// cout << w << endl;
		for(auto& v : H[w]) {
			// for(auto& x : v) cout << x << " ";
			// cout << endl;

			v.pb(-1);
			int j = sz(v) - 1;
			for(int i = sz(v) - 2; i >= 0; i--) {
				while(j - 1 >= 0 && (v[i] + w) < v[j - 1]) j--;
				nxt[v[i]][v[i] + w] = v[j];
			}
		}
		// cout << endl;
	}

	// for(int l = 0; l < N; l++) for(int r = l; r < N; r++) {
	// 	if (nxt[l][r] >= MOD) nxt[l][r] = -1;
	// 	// cout << l << " " << r << " " << nxt[l][r] << endl;
	// }


	for(int w = 0; w < N; w++) {
		for(int l = 0; l + w < N; l++) {
			int r = l + w;
			
			if (r-1 >= 0) dp[l][r] = min(dp[l][r], dp[l][r-1] + a);
			if (l+1 < N) dp[l][r] = min(dp[l][r], dp[l+1][r] + a);

			// cout << l << " " << r << " " << dp[l][r] << endl;

			int L = l; ll amt = 1;
			while(nxt[L][L + w] != -1) {
				L = nxt[L][L + w], amt++;
				ll left = (L + w - l + 1) - (l + w - l + 1) * amt;
				dp[l][L + w] = min(dp[l][L + w], dp[l][r] + b + c * amt + left * a);
				// cout << l << " " << l + w << " " << L << " " << L + w << " => " << dp[l][L + w] << endl;
			}
		}
	}

	cout << dp[0][N-1] << nl;

	exit(0-0);
}	

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