Submission #1018738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018738		Unforgettablepl	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	1753 ms	416036 KiB

copypaste3

#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,a,b,c;
	string s;
	cin >> n >> s >> a >> b >> c;
	s.insert(s.begin(),'$');
	vector<vector<int>> DP(n+1,vector<int>(n+1));
	for(int l=1;l<=n;l++)for(int r=l;r<=n;r++)DP[l][r]=a*(r-l+1ll);
	// Do the hashing stuff here
	map<pair<int,char>,int> hasher;
	vector<vector<int>> occurences = {{}};
	int alloc = 0;
	for(int l=1;l<=n;l++){
		int currhash = 0;
		for(int r=l;r<=n;r++){
			if(!hasher.count({currhash,s[r]})){
				hasher[{currhash,s[r]}]=++alloc;
				occurences.emplace_back();
			}
			currhash = hasher[{currhash,s[r]}];
			occurences[currhash].emplace_back(r);
		}
	}
	for(int l=n;l;l--){
		int currhash = 0;
		for(int r=l;r<=n;r++){
			currhash = hasher[{currhash,s[r]}];
			int len = r-l+1;
			if(l!=r){
				DP[l][r] = min(DP[l][r],DP[l+1][r]+a);
				DP[l][r] = min(DP[l][r],DP[l][r-1]+a);
			}
			auto iter = lower_bound(occurences[currhash].begin(),occurences[currhash].end(),r+len);
			int cnt = 1;
			while(iter!=occurences[currhash].end()){
				int x = *iter;
				cnt++;
				DP[l][x] = min(DP[l][x],DP[l][r]+b+a*(x-l+1ll - cnt*(len))+cnt*c);
				iter = lower_bound(occurences[currhash].begin(),occurences[currhash].end(),x+len);
			}
		}
	}
	cout << DP[1][n] << '\n';
}

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