oj.uz

Submission #548211

# Submission time Handle Problem Language Result Execution time Memory
548211 2022-04-12T17:58:15 Z inksamurai Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 1186 ms 282208 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3rfKJyA ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

//snuke's mod int
template <ll mod>
struct modint{
	ll x; // typedef long long ll;
	modint(ll x=0):x((x%mod+mod)%mod){}
	modint operator-()const{return modint(-x);}
	modint& operator+=(const modint a){if((x+=a.x)>=mod) x-=mod; return *this;}
	modint& operator-=(const modint a){if((x+=mod-a.x)>=mod) x-=mod; return *this;}
	modint& operator*=(const modint a){(x*=a.x)%=mod; return *this;}
	modint operator+(const modint a)const{modint res(*this); return res+=a;}
	modint operator-(const modint a)const{modint res(*this); return res-=a;}
	modint operator*(const modint a)const{modint res(*this); return res*=a;}
	modint pow(ll n)const{
		modint res=1,x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
};

// include mint here
using hshmint=modint<1000000007>;
using hshmint1=modint<998244353>;
using magicpair=pair<hshmint,hshmint1>;
hshmint _p=9973; // base
hshmint1 _p1=257; // base1
hshmint pw[3011],invpw[3011];
hshmint1 pw1[3011],invpw1[3011];
magicpair hsh[3011];

struct rollhsh{		
	rollhsh(string s=""){
		init(s);
	}
	void init(string s){
		// put this out in global if multiple testcases
		hsh[0]={1,1};
		pw[0]=1;
		pw1[0]=1;
		invpw[0]=1;
		invpw1[0]=1;		
		hshmint _invbase=_p.x;
		hshmint1 _invbase1=_p1.x;
		_invbase=_invbase.inv(); _invbase1=_invbase1.inv();
		rep(i,sz(s)){
			pw[i+1]=pw[i]*_p;
			pw1[i+1]=pw1[i]*_p1;
			invpw[i+1]=invpw[i]*_invbase;
			invpw1[i+1]=invpw1[i]*_invbase1;
			hshmint x=(int)(s[i]-'a'+1);
			hshmint1 x1=(int)(s[i]-'a'+1);
			hsh[i+1]={hsh[i].fi+pw[i]*x,hsh[i].se+pw1[i]*x1};
		}
	}
	pair<ll,ll> get(int l,int r){ 
		// from - to , inclusive
		hshmint _f=invpw[l]*(hsh[r+1].fi-hsh[l].fi);
		hshmint1 _s=invpw1[l]*(hsh[r+1].se-hsh[l].se);
		return {_f.x,_s.x};	
	}
};

signed main(){
_3rfKJyA;
	int n;
	cin>>n;
	
	string s;
	cin>>s;
	
	ll c0,c1,c2;
	cin>>c0>>c1>>c2;

	using pll=pair<ll,ll>;
	rollhsh nahsh(s);
	vec(vec(pll)) qol(n,vec(pll)(n));
	vec(pll) rbts;
	rep(i,n){
		rng(j,i,n){
			qol[i][j]=nahsh.get(i,j);
			rbts.pb(qol[i][j]);
		}
	}
	sort(rbts.begin(),rbts.end());
	rbts.erase(unique(rbts.begin(),rbts.end()));
	vec(vi) nxt(n,vi(n,-1));
	vi ptr(sz(rbts));
	for(int len=1;len<=n;len++){
		for(int i=0;i<n;i++){
			if(i+len-1>=n) break;
			int id=lower_bound(rbts.begin(),rbts.end(),qol[i][i+len-1])-rbts.begin();
			while(ptr[id]+len-1<i){
				if(qol[ptr[id]][ptr[id]+len-1].fi==qol[i][i+len-1].fi and qol[ptr[id]][ptr[id]+len-1].se==qol[i][i+len-1].se){
					nxt[ptr[id]][ptr[id]+len-1]=i;
				}
				ptr[id]+=1;
			}
		}
	}

	// cout<<nxt[2][3]<<"\n";

	const int inf=numeric_limits<int>::max();

	vec(vec(ll)) f(n,vec(ll)(n,inf)),g;
	g=f;
	for(int len=1;len<=n;len++){
		for(int i=0;i<n;i++){
			if(i+len-1>=n){
				break;
			}
			int j=i+len-1;
			if(len>1){
				g[i][j]=min({g[i][j],g[i+1][j],g[i][j-1]});
			}

			f[i][j]=len*c0;
			if(g[i][j]!=inf){
				f[i][j]=min(f[i][j],1ll*len*c0+g[i][j]);
			}

			ll cnt=1;
			int nj=i;
			while(1){
				g[i][nj+len-1]=min(g[i][nj+len-1],-1ll*len*c0*cnt+1ll*cnt*c2+f[i][i+len-1]+c1);
				nj=nxt[nj][nj+len-1];
				if(nj==-1) break;
				cnt+=1;
				// assert(cnt<=n/len);
			}
		}
	}

	print(f[0][n-1]);
//	
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 526 ms 151300 KB Output is correct
4 Correct 685 ms 176692 KB Output is correct
5 Correct 822 ms 206552 KB Output is correct
6 Correct 965 ms 241176 KB Output is correct
7 Correct 1184 ms 282208 KB Output is correct
8 Correct 1186 ms 282136 KB Output is correct
9 Correct 1180 ms 282160 KB Output is correct
10 Runtime error 1 ms 724 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Runtime error 1 ms 724 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Runtime error 1 ms 724 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Runtime error 1 ms 724 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 526 ms 151300 KB Output is correct
14 Correct 685 ms 176692 KB Output is correct
15 Correct 822 ms 206552 KB Output is correct
16 Correct 965 ms 241176 KB Output is correct
17 Correct 1184 ms 282208 KB Output is correct
18 Correct 1186 ms 282136 KB Output is correct
19 Correct 1180 ms 282160 KB Output is correct
20 Runtime error 1 ms 724 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -