Submission #548202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548202	2022-04-12T17:19:35 Z	inksamurai	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	3000 ms	175092 KB

copypaste3

#include <bits/stdc++.h>
#define int ll
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>;
struct rollhsh{	
	hshmint _p=9973; // base
	hshmint1 _p1=257; // base1
	vec(hshmint) pw,invpw;
	vec(hshmint1) pw1,invpw1;
	vec(magicpair) hsh;
	rollhsh(string s=""){
		init(s);
	}
	void init(string s){
		// put this out in global if multiple testcases
		hsh.clear();
		pw.clear();
		invpw.clear();
		pw1.clear();
		invpw1.clear();
		hsh.resize(sz(s)+1);
		pw.resize(sz(s)+1);
		invpw.resize(sz(s)+1);
		pw1.resize(sz(s)+1);
		invpw1.resize(sz(s)+1);
		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;
	
	int c0,c1,c2;
	cin>>c0>>c1>>c2;

	using pll=pair<ll,ll>;
	std::map<pll,vi> mp;
	rollhsh hsh(s);
	rep(i,n){
		rng(j,i,n){
			mp[hsh.get(i,j)].pb(i);
		}
	}

	const int inf=numeric_limits<int>::max();
	
	// so we want to minimize  -x * c * a + c * b + f[l][r]

	vec(vi) f(n,vi(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(i==0 and j==n-1) print("ho",f[i][j]);
			// cout<<c0<<"\n";
			if(g[i][j]!=inf){
				f[i][j]=min(f[i][j],len*c0+g[i][j]);
			}

			pll p=hsh.get(i,j);
			int cnt=1;
			j=i-1;
			while(1){
				auto it=upper_bound(mp[p].begin(),mp[p].end(),j);
				if(it==mp[p].end()){
					break;
				}
				int nj=*it+len-1;
				g[i][nj]=min(g[i][nj],-len*c0*cnt+cnt*c2+f[i][i+len-1]+c1);
				j=nj;
				cnt+=1;
			}
		}
	}

	print(f[0][n-1]);
	// cout<<f[0][1]<<"\n";
//	
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1338 ms	70548 KB	Output is correct
4	Correct	1617 ms	82092 KB	Output is correct
5	Correct	1974 ms	96612 KB	Output is correct
6	Correct	2268 ms	113284 KB	Output is correct
7	Correct	2673 ms	132452 KB	Output is correct
8	Correct	2642 ms	132556 KB	Output is correct
9	Correct	2630 ms	132456 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	316 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	324 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	1 ms	324 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	320 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	324 KB	Output is correct
32	Correct	1 ms	320 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	316 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	324 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	1 ms	324 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	320 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	324 KB	Output is correct
32	Correct	1 ms	320 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	316 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct
40	Correct	4 ms	704 KB	Output is correct
41	Correct	9 ms	1236 KB	Output is correct
42	Correct	20 ms	3016 KB	Output is correct
43	Correct	21 ms	3028 KB	Output is correct
44	Correct	20 ms	3028 KB	Output is correct
45	Correct	22 ms	3140 KB	Output is correct
46	Correct	21 ms	3124 KB	Output is correct
47	Correct	18 ms	1712 KB	Output is correct
48	Correct	22 ms	2324 KB	Output is correct
49	Correct	20 ms	2540 KB	Output is correct
50	Correct	19 ms	2516 KB	Output is correct
51	Correct	19 ms	2132 KB	Output is correct
52	Correct	20 ms	2240 KB	Output is correct
53	Correct	20 ms	3028 KB	Output is correct

Subtask #5
32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	320 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	324 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	1 ms	324 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	320 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	324 KB	Output is correct
32	Correct	1 ms	320 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	316 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct
40	Correct	4 ms	704 KB	Output is correct
41	Correct	9 ms	1236 KB	Output is correct
42	Correct	20 ms	3016 KB	Output is correct
43	Correct	21 ms	3028 KB	Output is correct
44	Correct	20 ms	3028 KB	Output is correct
45	Correct	22 ms	3140 KB	Output is correct
46	Correct	21 ms	3124 KB	Output is correct
47	Correct	18 ms	1712 KB	Output is correct
48	Correct	22 ms	2324 KB	Output is correct
49	Correct	20 ms	2540 KB	Output is correct
50	Correct	19 ms	2516 KB	Output is correct
51	Correct	19 ms	2132 KB	Output is correct
52	Correct	20 ms	2240 KB	Output is correct
53	Correct	20 ms	3028 KB	Output is correct
54	Correct	152 ms	14112 KB	Output is correct
55	Correct	355 ms	21580 KB	Output is correct
56	Correct	1218 ms	70044 KB	Output is correct
57	Correct	1230 ms	70396 KB	Output is correct
58	Correct	1229 ms	70624 KB	Output is correct
59	Correct	1214 ms	70620 KB	Output is correct
60	Correct	1215 ms	70792 KB	Output is correct
61	Correct	911 ms	44024 KB	Output is correct
62	Correct	358 ms	22384 KB	Output is correct
63	Correct	1118 ms	57656 KB	Output is correct
64	Correct	1098 ms	58392 KB	Output is correct
65	Correct	1022 ms	45140 KB	Output is correct
66	Correct	1036 ms	45208 KB	Output is correct
67	Correct	1184 ms	70692 KB	Output is correct

Subtask #6
0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1338 ms	70548 KB	Output is correct
14	Correct	1617 ms	82092 KB	Output is correct
15	Correct	1974 ms	96612 KB	Output is correct
16	Correct	2268 ms	113284 KB	Output is correct
17	Correct	2673 ms	132452 KB	Output is correct
18	Correct	2642 ms	132556 KB	Output is correct
19	Correct	2630 ms	132456 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	0 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	316 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	0 ms	212 KB	Output is correct
28	Correct	0 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	1 ms	320 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	324 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	0 ms	212 KB	Output is correct
37	Correct	0 ms	212 KB	Output is correct
38	Correct	1 ms	324 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct
40	Correct	1 ms	340 KB	Output is correct
41	Correct	1 ms	340 KB	Output is correct
42	Correct	1 ms	340 KB	Output is correct
43	Correct	1 ms	340 KB	Output is correct
44	Correct	1 ms	340 KB	Output is correct
45	Correct	1 ms	340 KB	Output is correct
46	Correct	1 ms	320 KB	Output is correct
47	Correct	1 ms	340 KB	Output is correct
48	Correct	1 ms	324 KB	Output is correct
49	Correct	1 ms	320 KB	Output is correct
50	Correct	1 ms	340 KB	Output is correct
51	Correct	1 ms	212 KB	Output is correct
52	Correct	1 ms	316 KB	Output is correct
53	Correct	0 ms	212 KB	Output is correct
54	Correct	1 ms	212 KB	Output is correct
55	Correct	1 ms	212 KB	Output is correct
56	Correct	1 ms	340 KB	Output is correct
57	Correct	4 ms	704 KB	Output is correct
58	Correct	9 ms	1236 KB	Output is correct
59	Correct	20 ms	3016 KB	Output is correct
60	Correct	21 ms	3028 KB	Output is correct
61	Correct	20 ms	3028 KB	Output is correct
62	Correct	22 ms	3140 KB	Output is correct
63	Correct	21 ms	3124 KB	Output is correct
64	Correct	18 ms	1712 KB	Output is correct
65	Correct	22 ms	2324 KB	Output is correct
66	Correct	20 ms	2540 KB	Output is correct
67	Correct	19 ms	2516 KB	Output is correct
68	Correct	19 ms	2132 KB	Output is correct
69	Correct	20 ms	2240 KB	Output is correct
70	Correct	20 ms	3028 KB	Output is correct
71	Correct	152 ms	14112 KB	Output is correct
72	Correct	355 ms	21580 KB	Output is correct
73	Correct	1218 ms	70044 KB	Output is correct
74	Correct	1230 ms	70396 KB	Output is correct
75	Correct	1229 ms	70624 KB	Output is correct
76	Correct	1214 ms	70620 KB	Output is correct
77	Correct	1215 ms	70792 KB	Output is correct
78	Correct	911 ms	44024 KB	Output is correct
79	Correct	358 ms	22384 KB	Output is correct
80	Correct	1118 ms	57656 KB	Output is correct
81	Correct	1098 ms	58392 KB	Output is correct
82	Correct	1022 ms	45140 KB	Output is correct
83	Correct	1036 ms	45208 KB	Output is correct
84	Correct	1184 ms	70692 KB	Output is correct
85	Execution timed out	3037 ms	175092 KB	Time limit exceeded
86	Halted	0 ms	0 KB	-

Submission #548202

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 5.0 / 5.0

Subtask #3 14.0 / 14.0

Subtask #4 10.0 / 10.0

Subtask #5 32.0 / 32.0

Subtask #6 0 / 38.0

Subtask #1
1.0 / 1.0

Subtask #2
5.0 / 5.0

Subtask #3
14.0 / 14.0

Subtask #4
10.0 / 10.0

Subtask #5
32.0 / 32.0

Subtask #6
0 / 38.0