답안 #548209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548209	2022-04-12T17:41:55 Z	inksamurai	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	3000 ms	184916 KB

copypaste3

#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>;
	std::map<pll,vi> mp;
	rollhsh nahsh(s);
	rep(i,n){
		rng(j,i,n){
			mp[nahsh.get(i,j)].pb(i);
		}
	}

	vec(vi) nxt(n,vi(n,-1));
	rep(i,n){
		rng(j,i,n){
			pll p=nahsh.get(i,j);
			auto it=upper_bound(mp[p].begin(),mp[p].end(),j);
			if(it!=mp[p].end()){
				nxt[i][j]=*it;
			}
		}
	}

	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;
			}
		}
	}

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

Subtask #1
1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 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	1 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	1 ms	340 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	825 ms	75544 KB	Output is correct
4	Correct	1036 ms	87832 KB	Output is correct
5	Correct	1290 ms	102744 KB	Output is correct
6	Correct	1579 ms	120408 KB	Output is correct
7	Correct	1813 ms	140716 KB	Output is correct
8	Correct	1835 ms	140836 KB	Output is correct
9	Correct	1802 ms	140832 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 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

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 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	1 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	1 ms	340 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	456 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	Correct	0 ms	456 KB	Output is correct
19	Correct	0 ms	468 KB	Output is correct
20	Correct	0 ms	352 KB	Output is correct
21	Correct	1 ms	468 KB	Output is correct
22	Correct	1 ms	468 KB	Output is correct
23	Correct	1 ms	468 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	1 ms	468 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	1 ms	456 KB	Output is correct
33	Correct	1 ms	468 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	0 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	340 KB	Output is correct
39	Correct	1 ms	468 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 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	1 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	1 ms	340 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	456 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	Correct	0 ms	456 KB	Output is correct
19	Correct	0 ms	468 KB	Output is correct
20	Correct	0 ms	352 KB	Output is correct
21	Correct	1 ms	468 KB	Output is correct
22	Correct	1 ms	468 KB	Output is correct
23	Correct	1 ms	468 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	1 ms	468 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	1 ms	456 KB	Output is correct
33	Correct	1 ms	468 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	0 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	340 KB	Output is correct
39	Correct	1 ms	468 KB	Output is correct
40	Correct	2 ms	852 KB	Output is correct
41	Correct	5 ms	1424 KB	Output is correct
42	Correct	16 ms	3336 KB	Output is correct
43	Correct	19 ms	3376 KB	Output is correct
44	Correct	16 ms	3424 KB	Output is correct
45	Correct	17 ms	3540 KB	Output is correct
46	Correct	17 ms	3448 KB	Output is correct
47	Correct	12 ms	1868 KB	Output is correct
48	Correct	17 ms	2548 KB	Output is correct
49	Correct	13 ms	2772 KB	Output is correct
50	Correct	14 ms	2768 KB	Output is correct
51	Correct	13 ms	2548 KB	Output is correct
52	Correct	12 ms	2468 KB	Output is correct
53	Correct	14 ms	3412 KB	Output is correct

Subtask #5
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 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	1 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	1 ms	340 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	456 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	Correct	0 ms	456 KB	Output is correct
19	Correct	0 ms	468 KB	Output is correct
20	Correct	0 ms	352 KB	Output is correct
21	Correct	1 ms	468 KB	Output is correct
22	Correct	1 ms	468 KB	Output is correct
23	Correct	1 ms	468 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	1 ms	468 KB	Output is correct
28	Correct	1 ms	468 KB	Output is correct
29	Correct	1 ms	468 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	1 ms	456 KB	Output is correct
33	Correct	1 ms	468 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	0 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	340 KB	Output is correct
39	Correct	1 ms	468 KB	Output is correct
40	Correct	2 ms	852 KB	Output is correct
41	Correct	5 ms	1424 KB	Output is correct
42	Correct	16 ms	3336 KB	Output is correct
43	Correct	19 ms	3376 KB	Output is correct
44	Correct	16 ms	3424 KB	Output is correct
45	Correct	17 ms	3540 KB	Output is correct
46	Correct	17 ms	3448 KB	Output is correct
47	Correct	12 ms	1868 KB	Output is correct
48	Correct	17 ms	2548 KB	Output is correct
49	Correct	13 ms	2772 KB	Output is correct
50	Correct	14 ms	2768 KB	Output is correct
51	Correct	13 ms	2548 KB	Output is correct
52	Correct	12 ms	2468 KB	Output is correct
53	Correct	14 ms	3412 KB	Output is correct
54	Correct	115 ms	14936 KB	Output is correct
55	Correct	186 ms	22860 KB	Output is correct
56	Correct	994 ms	73928 KB	Output is correct
57	Correct	979 ms	74308 KB	Output is correct
58	Correct	979 ms	74688 KB	Output is correct
59	Correct	1006 ms	74664 KB	Output is correct
60	Correct	964 ms	74712 KB	Output is correct
61	Correct	738 ms	43400 KB	Output is correct
62	Correct	240 ms	23592 KB	Output is correct
63	Correct	858 ms	61388 KB	Output is correct
64	Correct	868 ms	61952 KB	Output is correct
65	Correct	866 ms	47544 KB	Output is correct
66	Correct	809 ms	47540 KB	Output is correct
67	Correct	977 ms	74708 KB	Output is correct

Subtask #6
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 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	1 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	1 ms	340 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	468 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	825 ms	75544 KB	Output is correct
14	Correct	1036 ms	87832 KB	Output is correct
15	Correct	1290 ms	102744 KB	Output is correct
16	Correct	1579 ms	120408 KB	Output is correct
17	Correct	1813 ms	140716 KB	Output is correct
18	Correct	1835 ms	140836 KB	Output is correct
19	Correct	1802 ms	140832 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 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	468 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	456 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	468 KB	Output is correct
33	Correct	1 ms	468 KB	Output is correct
34	Correct	0 ms	340 KB	Output is correct
35	Correct	0 ms	456 KB	Output is correct
36	Correct	0 ms	468 KB	Output is correct
37	Correct	0 ms	352 KB	Output is correct
38	Correct	1 ms	468 KB	Output is correct
39	Correct	1 ms	468 KB	Output is correct
40	Correct	1 ms	468 KB	Output is correct
41	Correct	1 ms	468 KB	Output is correct
42	Correct	1 ms	468 KB	Output is correct
43	Correct	1 ms	468 KB	Output is correct
44	Correct	1 ms	468 KB	Output is correct
45	Correct	1 ms	468 KB	Output is correct
46	Correct	1 ms	468 KB	Output is correct
47	Correct	1 ms	468 KB	Output is correct
48	Correct	1 ms	468 KB	Output is correct
49	Correct	1 ms	456 KB	Output is correct
50	Correct	1 ms	468 KB	Output is correct
51	Correct	1 ms	340 KB	Output is correct
52	Correct	1 ms	340 KB	Output is correct
53	Correct	0 ms	340 KB	Output is correct
54	Correct	1 ms	340 KB	Output is correct
55	Correct	1 ms	340 KB	Output is correct
56	Correct	1 ms	468 KB	Output is correct
57	Correct	2 ms	852 KB	Output is correct
58	Correct	5 ms	1424 KB	Output is correct
59	Correct	16 ms	3336 KB	Output is correct
60	Correct	19 ms	3376 KB	Output is correct
61	Correct	16 ms	3424 KB	Output is correct
62	Correct	17 ms	3540 KB	Output is correct
63	Correct	17 ms	3448 KB	Output is correct
64	Correct	12 ms	1868 KB	Output is correct
65	Correct	17 ms	2548 KB	Output is correct
66	Correct	13 ms	2772 KB	Output is correct
67	Correct	14 ms	2768 KB	Output is correct
68	Correct	13 ms	2548 KB	Output is correct
69	Correct	12 ms	2468 KB	Output is correct
70	Correct	14 ms	3412 KB	Output is correct
71	Correct	115 ms	14936 KB	Output is correct
72	Correct	186 ms	22860 KB	Output is correct
73	Correct	994 ms	73928 KB	Output is correct
74	Correct	979 ms	74308 KB	Output is correct
75	Correct	979 ms	74688 KB	Output is correct
76	Correct	1006 ms	74664 KB	Output is correct
77	Correct	964 ms	74712 KB	Output is correct
78	Correct	738 ms	43400 KB	Output is correct
79	Correct	240 ms	23592 KB	Output is correct
80	Correct	858 ms	61388 KB	Output is correct
81	Correct	868 ms	61952 KB	Output is correct
82	Correct	866 ms	47544 KB	Output is correct
83	Correct	809 ms	47540 KB	Output is correct
84	Correct	977 ms	74708 KB	Output is correct
85	Execution timed out	3089 ms	184916 KB	Time limit exceeded
86	Halted	0 ms	0 KB	-

답안 #548209

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