Submission #733894

#	Time	Username	Problem	Language	Result	Execution time	Memory
733894		QwertyPi	Copy and Paste 3 (JOI22_copypaste3)	C++14	30 / 100	2371 ms	67412 KiB

copypaste3

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 1LL << 60;
int dp[2501][2501];
int chmin(int& x, int y){
	return x = min(x, y);
}

const int a = 32913, m = 1e9 + 7;
int pw[2501], h[2501];

int ha(int l, int len){
	return ((h[l + len] - h[l] * pw[len]) % m + m) % m;
}

int H[2501][2501];

int32_t main(){
	int n; string s; cin >> n >> s;
	int A, B, C; cin >> A >> B >> C; 
	pw[0] = 1; 
	for(int i = 0; i < n; i++) 
		pw[i + 1] = pw[i] * a % m, h[i + 1] = (h[i] * a + s[i]) % m;
	
	for(int l = 0; l < n; l++){
		for(int r = l; r < n; r++){
			H[l][r] = ha(l, r - l + 1);
		}
	}
	
	for(int sz = 2; sz <= n; sz++){
		for(int l = 0; l <= n - sz; l++){
			dp[l][l + sz - 1] = INF;
		}
	}
	
	for(int sz = 1; sz <= n; sz++){
		
		if(sz != 1){
			for(int l = 0; l <= n - sz; l++){
				int r = l + sz - 1;
				dp[l][r] = min(dp[l][r], min(dp[l][r - 1], dp[l + 1][r]) + A);
			}
		}else{
			for(int l = 0; l < n; l++) dp[l][l] = A;
		}
		
		unordered_map<int, vector<int>> M;
		for(int l = 0; l <= n - sz; l++){
			M[ha(l, sz)].push_back(l);
		}
		for(auto& [h, v] : M){
			int k = v.size();
			for(int l = 0; l < k; l++){
				int _acc = 0, _max = -1;
				for(int r = l; r < k; r++){
					if(v[r] > _max){
						_acc++; _max = v[r] + sz - 1;
						dp[v[l]][_max] = min(dp[v[l]][_max], dp[v[l]][v[l] + sz - 1] + (_max - v[l] + 1 - _acc * sz) * A + B + _acc * C);
					}
				}
			}
		}
	}
	cout << dp[0][n - 1] << endl;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int32_t main()':
copypaste3.cpp:54:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   for(auto& [h, v] : M){
      |             ^

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