Submission #1206654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206654		PenguinsAreCute	Copy and Paste 3 (JOI22_copypaste3)	C++17	57 / 100	3061 ms	54160 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
using i6 = long long;
using i7 = __int128;
const i6 MOD = 1e15 + 37;
const i6 BASE = 267;
i6 exp(i6 a, i6 b) {return (b?(i7(exp(i7(a)*a%MOD,b/2))*(b&1?a:1)%MOD):1);}
int main() {
	int n, a, b, c;
	string s;
	cin >> n >> s >> a >> b >> c;
	i6 pre[n+1];
	pre[0] = 0;
	i6 bpow[n+1], ipow[n+1];
	bpow[0] = ipow[0] = 1;
	for(int i=1;i<=n;i++) {
		bpow[i] = i7(1) * bpow[i-1] * BASE % MOD;
		ipow[i] = exp(bpow[i], MOD - 2);
	}
	for(int i=0;i<n;i++)
		pre[i+1] = (pre[i] + i7(bpow[i]) * s[i]) % MOD;

	int prev[n][n];
	memset(prev,-1,sizeof(prev));
	for(int l=0;l<n;l++) {
		i6 cur[n-l], cpy[n-l];
		for(int i=0;i<n-l;i++) {
			cur[i] = (pre[i + l + 1] - pre[i] + MOD) % MOD;
			cur[i] = (i7(cur[i]) * ipow[i]) % MOD;
		}
		memcpy(cpy,cur,sizeof(cpy));
		sort(cpy,cpy+n-l);
		vector<int> occ[n-l];
		for(int i=0;i<n-l;i++) {
			cur[i] = lower_bound(cpy,cpy+n-l,cur[i])-cpy;
			occ[cur[i]].push_back(i);
			auto it = lower_bound(occ[cur[i]].begin(),occ[cur[i]].end(),i-l);
			prev[i][i+l]=(it==occ[cur[i]].begin()?-1:*(--it));
		}
	}
	i6 dp[n][n];
	memset(dp,0,sizeof(dp));
	for(int j=1;j<n;j++) {
		for(int i=j;~i;i--) {
			dp[i][j] = min(dp[i][j], dp[i][j-1]);
			i6 t = dp[i][j] + a * (j - i + 1LL) + b;
			i6 nxt = i, cnt = 0;
			for(int k=i;~k;k--)  {
				if(k == nxt) {
					nxt = prev[k][k + j - i];
					cnt++;
				}
				dp[k][j] = min(dp[k][j], t + (c - a * (j - i + 1LL)) * cnt);
			}
		}
	}
	cout << dp[0][n-1] + 1LL * n * a;
}

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