Submission #1206661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206661		PenguinsAreCute	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	1191 ms	123132 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);}
struct seg {
	int n;
	vector<i6> v;
	seg(int _n): n(_n), v(2*_n,0) {}
	void up(int l, int r, i6 u) {
		for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
			if(l&1) {
				v[l] = min(v[l], u);
				l++;
			}
			if(r&1) {
				r--;
				v[r] = min(v[r], u);
			}
		}
	}
	i6 qry(int x) {
		i6 ans = 0;
		for(x+=n;x;x>>=1)
			ans = min(ans, v[x]);
		return ans;
	}
};
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));
		}
	}
	vector<seg> dp(n,seg(n));
	for(int j=1;j<n;j++) {
		for(int i=j;~i;i--) {
			dp[j].up(i,i+1,dp[j-1].qry(i));
			i6 t = dp[j].qry(i) + a * (j - i + 1LL) + b;
			i6 nxt = i, cnt = 0;
			while(~nxt) {
				i6 nw = prev[nxt][nxt + j - i];
				cnt++;
				dp[j].up(nw + 1, nxt + 1, t + (c - a * (j - i + 1LL)) * cnt);
				nxt = nw;
			}
		}
	}
	cout << dp[n-1].qry(0) + 1LL * n * a;
}

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