Submission #567729

#	Time	Username	Problem	Language	Result	Execution time	Memory
567729		errorgorn	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	1402 ms	98800 KiB

copypaste3

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
string s;
int a,b,c;

int memo[2505][2505]; //the answer
int nxt[2505][2505]; //(length,index)

void proc(vector<int> v,int len){
	sort(all(v));
	reverse(all(v));
	
	int idx=-1;
	for (auto it:v){
		if (it+len<=v[idx+1]) idx++;
		if (idx!=-1) nxt[len][it]=v[idx];
	}
	
	//cout<<len<<": "<<endl;
	//for (auto it:v) cout<<it<<" "; cout<<endl;
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>s;
	cin>>a>>b>>c;
	
	vector<int> idx;
	rep(x,0,n) idx.pub(x);
	
	sort(all(idx),[](int i,int j){ //poor man's suffix array
		return s.substr(i,n-i)<s.substr(j,n-j);
	});
	
	//for (auto it:idx) cout<<it<<" "; cout<<endl;
	
	memset(nxt,-1,sizeof(nxt));
	rep(x,1,n+1){
		vector<int> temp;
		for (auto it:idx) if (it+x<=n) temp.pub(it);
		rep(y,0,sz(temp)-1) assert(s.substr(temp[y],x)<=s.substr(temp[y+1],x));
		temp.clear();
		
		for (auto it:idx) if (it+x<=n){
			if (!temp.empty() && s.substr(temp.back(),x)!=s.substr(it,x)){
				proc(temp,x);
				temp.clear();
			}
			
			temp.pub(it);
		}
		proc(temp,x);
	}
	
	//rep(x,1,n+1){
		//rep(y,0,n) cout<<nxt[x][y]<<" "; cout<<endl;
	//}
	
	memset(memo,1,sizeof(memo));
	
	rep(x,0,n) memo[x][x]=a;
	rep(len,1,n+1){
		rep(l,0,n+1-len){
			int r=l+len-1;
			
			if (l!=0) memo[l-1][r]=min(memo[l-1][r],memo[l][r]+a);
			if (r!=n-1) memo[l][r+1]=min(memo[l][r+1],memo[l][r]+a);
			
			int curr=l;
			int num=1;
			while (nxt[len][curr]!=-1){
				curr=nxt[len][curr];
				num++;
				
				int r2=curr+len-1;
				memo[l][r2]=min(memo[l][r2],
					memo[l][r]+b+num*c+(r2-l+1-num*len)*a);
			}
		}
	}
	
	cout<<memo[0][n-1]<<endl;
}

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