Submission #1210929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210929		salmon	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	1006 ms	415108 KiB

copypaste3

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

int N;
string s;
int A;
int B;
int C;
int cont = 0;
vector<int> pos[10100100];
long long int memo[10100100];
long long int cost[2600][2600];
int cod[2600][2600];
int l[10100100];
int nex[2600][2600];
long long int inf = 1.1e18;

void split(int it, vector<int> v){
	
	if(it != 0){
		int temp = cont;
		cont++;
		
		l[temp] = it;
		for(int j : v) cod[j][it + j - 1] = temp;
	}
	
	vector<int> a[26];
	
	for(int j : v) if(j + it < N) a[s[j + it]].push_back(j);
	
	for(int i = 0; i < 26; i++){
		if(a[i].empty()) continue;
		split(it + 1, a[i]);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N;
	cin >> s;
	
	cin >> A;
	cin >> B;
	cin >> C;
		
	for(int i = 0; i < N; i++){
		s[i] -= 'a';
	}
	
	vector<int> temp;
	
	for(int i = 0; i < N; i++) temp.push_back(i);
	
	split(0,temp);
	
	/*for(int i = 0; i < N; i++){
		for(int j = 0; i + j < N; j++){
			printf("%d ",cod[j][i + j]);
		}
		printf("\n");
	}*/
	
	for(int i = 0; i < cont ; i++){
		memo[i] = inf;
	}
	
	for(int j = 0; j < N; j++){
		memo[cod[j][j]] = A;
	}
	
	for(int j = 0; j < N; j++){
		for(int i = 0; i + j < N; i++){
			pos[cod[i][i + j]].push_back(i);
		}
	}

	for(int i = 0; i < cont; i++){
		int it = 0;
		int len = l[i];
		
		for(int j : pos[i]){
			while(it != pos[i].size() && pos[i][it] < j + len){
				it++;
			}	
			
			if(it == pos[i].size()) nex[j][j + len - 1] = -1;
			else nex[j][j + len - 1] = pos[i][it];
		}
	}
	
	for(int j = 0; j < N; j++){
		for(int i = 0; i + j < N; i++){
			int pos = i;
			long long int c = memo[cod[i][i + j]] + B + C;
			
			while(nex[pos][pos + j] != -1){
				c += (nex[pos][pos + j] - (pos + j) - 1) * (long long int)A;
				pos = nex[pos][pos + j];
				c += C;
				memo[cod[i][pos + j]] = min(memo[cod[i][pos + j]], c);
			}
		
			if(i + j != N - 1) memo[cod[i][i + j + 1]] = min(memo[cod[i][i + j + 1]], memo[cod[i][i + j]] + A);
			if(i != 0) memo[cod[i - 1][i + j]] = min(memo[cod[i - 1][i + j]], memo[cod[i][i + j]] + A);
		}
	}
	
	/*for(int i = 0; i < cont; i++){
		printf("%d %lld\n",i,memo[i]);
	}*/
	
	printf("%lld\n",memo[cod[0][N-1]]);
}

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