oj.uz

Submission #548212

# Submission time Handle Problem Language Result Execution time Memory
548212 2022-04-12T18:00:13 Z inksamurai Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 1287 ms 282320 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();
			assert(id!=-1);
			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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 572 ms 151176 KB Output is correct
4 Correct 693 ms 176732 KB Output is correct
5 Correct 857 ms 206556 KB Output is correct
6 Correct 1029 ms 241312 KB Output is correct
7 Correct 1287 ms 282232 KB Output is correct
8 Correct 1249 ms 282312 KB Output is correct
9 Correct 1257 ms 282320 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 1 ms 468 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 1 ms 468 KB Output is correct
16 Correct 1 ms 468 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 1 ms 468 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 1 ms 468 KB Output is correct
16 Correct 1 ms 468 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 1 ms 468 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 1 ms 468 KB Output is correct
16 Correct 1 ms 468 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 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 1 ms 468 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 572 ms 151176 KB Output is correct
14 Correct 693 ms 176732 KB Output is correct
15 Correct 857 ms 206556 KB Output is correct
16 Correct 1029 ms 241312 KB Output is correct
17 Correct 1287 ms 282232 KB Output is correct
18 Correct 1249 ms 282312 KB Output is correct
19 Correct 1257 ms 282320 KB Output is correct
20 Runtime error 1 ms 724 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -