Submission #1206650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206650		PenguinsAreCute	Copy and Paste 3 (JOI22_copypaste3)	C++17	0 / 100	0 ms	324 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++) {
		unordered_map<i6,int> m;
		for(int i=0;i<n-l;i++) {
			i6 cur = (pre[i + l + 1] - pre[i] + MOD) % MOD;
			cur = (i7(cur) * ipow[i]) % MOD;
			if(!m.count(cur))
				prev[i][i+l] = -1;
			else
				prev[i][i+l] = m[cur];
			m[cur] = i;
		}
	}
	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: 0 / 1
• Subtask 2: 0 / 5
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38