Submission #714423

#	Time	Username	Problem	Language	Result	Execution time	Memory
714423		089487	Copy and Paste 3 (JOI22_copypaste3)	C++14	62 / 100	3076 ms	384928 KiB

copypaste3

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=25e2+7;
const int INF=1e18;
const int p=29;
const int Mod=462'779'347'772'851;
int pref[N][N];
int dp[N][N];
string s;
const int M=1e7;
vector<int> v[M];
void build(int n){
	rep(i,1,n){
		rep(j,i,n){
			pref[i][j]=pref[i][j-1]*p%Mod+s[j-1]-'a'+2;
			if(pref[i][j]>=Mod) pref[i][j]-=Mod;
		}
	}
}
int nxt[N];
bool vis[M];
signed main(){
	quick 
	int n;
	cin>>n;
	cin>>s;
	double St=clock();
	build(n);
	int a,b,c;
	cin>>a>>b>>c;
	map<int,int > mx;
	int cnt=1;
	rep(i,1,n){
		rep(j,i,n){
			dp[i][j]=(j-i+1)*a;
			if(!mx[pref[i][j]]) mx[pref[i][j]]=cnt++;
			v[mx[pref[i][j]]].eb(i);
		}
	}
	rep(L,1,n){
		fill(nxt,nxt+n+1,-1);
		rep(l,1,n-L+1){
			int r=l+L-1;
			int qx=mx[pref[l][r]];
			int n2=sz(v[qx]);
			if(l<r) dp[l][r]=min({dp[l][r],dp[l][r-1]+a,dp[l+1][r]+a});
			if(!vis[qx]&&n2!=1){
				int _r=0;
				int n2=sz(v[qx]);
				rep(i,0,n2-1){
					while(_r<n2&&v[qx][_r]<=v[qx][i]+L-1) _r++;
					nxt[v[qx][i]]=(_r>=n2 ? -1 : v[qx][_r]);
				}
				vis[qx]=true;
			}
			int px=nxt[l];
			int pst=1;
			while(px!=-1){
				dp[l][px+L-1]=min(dp[l][px+L-1],(px-l-pst*L)*a+pst*c+b+c+dp[l][r]);
				pst++;
				px=nxt[px];
			}
			if((clock()-St)/CLOCKS_PER_SEC>=2.8) break;
		}
		if((clock()-St)/CLOCKS_PER_SEC>=2.8) break;
	}
	cout<<dp[1][n]<<"\n";
	return 0;
}

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