Submission #1318020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318020		i271828	Copy and Paste 3 (JOI22_copypaste3)	C++20	1 / 100	1760 ms	34644 KiB

copypaste3

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

const int MAX=2505;
const int LOG=15;

int N;
ll CA,CB,CC;
int A[MAX];
int nxt[MAX][MAX];
ll dp[MAX][MAX];
priority_queue<pii,vector<pii>,greater<pii>> pq;
set<pair<ll,int>> st;
ll V[MAX];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>N;
	for (int i=0;i<N;i++){
		char c;cin>>c;
		A[i]=c-'a';
	}
	cin>>CA>>CB>>CC;
	for (int l=N-1;l>=0;l--){
		int x;
		for (x=l+1;x<N;x++) if (A[x]==A[l]) break;
		nxt[l][l]=x;
		for (int r=l+1;r<N;r++){
			while (x-l+r<N&&(x<=r||A[x-l+r]!=A[r])) x=nxt[x][x-l+(r-1)];
			if (x-l+r>=N) x=N;
			nxt[l][r]=x;
		}
	}
	for (int l=N-1;l>=0;l--){
		while (pq.size()) pq.pop();
		st.clear();
		for (int r=l;r<N;r++){
			dp[l][r]=dp[l+1][r]+CA;
			while (pq.size()&&pq.top().first<=r){
				auto [_,x]=pq.top();
				pq.pop();
				pq.push({nxt[r-x+l][r]-l+x,x});
				st.erase({V[x],x});
				V[x]+=CC-(x-l+1)*CA;
				st.insert({V[x],x});
			}
			if (st.size()){
				dp[l][r]=min(dp[l][r],(r-l+1)*CA+st.begin()->first);
			}
			V[r]=dp[l][r]+CB+CC-(r-l+1)*CA;
			st.insert({V[r],r});
			pq.push({nxt[l][r]-l+r,r});
		}
	}
	cout<<dp[0][N-1]<<'\n';
}

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