답안 #855340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855340	2023-10-01T06:12:57 Z	willychan	Chorus (JOI23_chorus)	C++14	100 / 100	3651 ms	36668 KB

chorus

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
const int N = 1e6+5;
pair<ll,ll> dp[N];
int Bpa[N];
ll Bpasum[N];
int Bpaj[N];
int n,K;

ll cost(int i,int j){
	int r = min(Bpaj[j],j);
	int l = i+1;
	if(r<l) return 0;
	return (1LL*j*(r-l+1))-(Bpasum[r]-Bpasum[l-1]);
}

struct seg{
	int pos;int l;int r;
	seg(int _pos,int _l,int _r):pos(_pos),l(_l),r(_r){}
};

bool ok(ll v){
	for(int i=0;i<=n;i++) dp[i] = {1e18,0};
	dp[0]={0,0};
	dp[n+1] = {1e15,0};
	deque<seg> dq;
	dq.push_back(seg(0,1,n));
	for(int i=1;i<=n;i++){
		while(dq.size()){
			if(dq[0].r<i) dq.pop_front();
			else break;
		}
		dp[i] = {dp[dq[0].pos].first+cost(dq[0].pos,i)+v,dp[dq[0].pos].second+1};
		while(dq.size()){
			if(dp[dq.back().pos].first+cost(dq.back().pos,dq.back().l)>dp[i].first+cost(i,dq.back().l)) dq.pop_back();
			else break;
		}
		if(dq.empty()) dq.push_back(seg(i,i+1,n));
		else{
			seg pseg = dq.back();
			dq.pop_back();
			ll l = pseg.l;ll r = pseg.r+1;
			while(r-l>1){
				ll mid = (l+r)/2;
				if(dp[pseg.pos].first+cost(pseg.pos,mid)>dp[i].first+cost(i,mid)) r=mid;
				else l = mid;
			}
			dq.push_back(seg(pseg.pos,pseg.l,l));
			if(l!=n) dq.push_back(seg(i,l+1,n));
		}
	}
	return (dp[n].second<=K);
}
 
signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>K;			
	string s;cin>>s;
	int pa = 0;
	int pb = 0;
	for(int i=1;i<=2*n;i++){
		if(s[i-1]=='A') Bpaj[pa++]=pb;
		if(s[i-1]=='B') Bpa[++pb]=pa;
	}
	for(int i=pa;i<=n;i++) Bpaj[i]=n;
	for(int i=1;i<=n;i++){
		Bpasum[i] = Bpasum[i-1]+Bpa[i];
	}
	ll l = -1;ll r = 1LL*n*n+2;
	while(r-l>1){
		ll mid = l+((r-l)/2);
		if(ok(mid)) r = mid;
		else l = mid;
	}
	ok(r);
	//cout<<r<<"\n";
	cout<<dp[n].first-(1LL*r*K)<<"\n";
 
	return 0;
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4440 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4440 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	1 ms	4444 KB	Output is correct
18	Correct	1 ms	4696 KB	Output is correct
19	Correct	1 ms	4444 KB	Output is correct
20	Correct	1 ms	4440 KB	Output is correct
21	Correct	1 ms	4444 KB	Output is correct
22	Correct	1 ms	4444 KB	Output is correct
23	Correct	1 ms	4444 KB	Output is correct
24	Correct	1 ms	4444 KB	Output is correct
25	Correct	1 ms	4444 KB	Output is correct
26	Correct	1 ms	4444 KB	Output is correct
27	Correct	1 ms	4444 KB	Output is correct
28	Correct	1 ms	4444 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4440 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	1 ms	4444 KB	Output is correct
18	Correct	1 ms	4696 KB	Output is correct
19	Correct	1 ms	4444 KB	Output is correct
20	Correct	1 ms	4440 KB	Output is correct
21	Correct	1 ms	4444 KB	Output is correct
22	Correct	1 ms	4444 KB	Output is correct
23	Correct	1 ms	4444 KB	Output is correct
24	Correct	1 ms	4444 KB	Output is correct
25	Correct	1 ms	4444 KB	Output is correct
26	Correct	1 ms	4444 KB	Output is correct
27	Correct	1 ms	4444 KB	Output is correct
28	Correct	1 ms	4444 KB	Output is correct
29	Correct	8 ms	4444 KB	Output is correct
30	Correct	9 ms	4444 KB	Output is correct
31	Correct	9 ms	4664 KB	Output is correct
32	Correct	8 ms	4664 KB	Output is correct
33	Correct	7 ms	4444 KB	Output is correct
34	Correct	8 ms	4444 KB	Output is correct
35	Correct	9 ms	4440 KB	Output is correct
36	Correct	9 ms	4444 KB	Output is correct
37	Correct	9 ms	4664 KB	Output is correct
38	Correct	9 ms	4440 KB	Output is correct
39	Correct	8 ms	4640 KB	Output is correct
40	Correct	7 ms	4444 KB	Output is correct
41	Correct	6 ms	4444 KB	Output is correct
42	Correct	7 ms	4444 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4440 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	1 ms	4444 KB	Output is correct
18	Correct	1 ms	4696 KB	Output is correct
19	Correct	1 ms	4444 KB	Output is correct
20	Correct	1 ms	4440 KB	Output is correct
21	Correct	1 ms	4444 KB	Output is correct
22	Correct	1 ms	4444 KB	Output is correct
23	Correct	1 ms	4444 KB	Output is correct
24	Correct	1 ms	4444 KB	Output is correct
25	Correct	1 ms	4444 KB	Output is correct
26	Correct	1 ms	4444 KB	Output is correct
27	Correct	1 ms	4444 KB	Output is correct
28	Correct	1 ms	4444 KB	Output is correct
29	Correct	8 ms	4444 KB	Output is correct
30	Correct	9 ms	4444 KB	Output is correct
31	Correct	9 ms	4664 KB	Output is correct
32	Correct	8 ms	4664 KB	Output is correct
33	Correct	7 ms	4444 KB	Output is correct
34	Correct	8 ms	4444 KB	Output is correct
35	Correct	9 ms	4440 KB	Output is correct
36	Correct	9 ms	4444 KB	Output is correct
37	Correct	9 ms	4664 KB	Output is correct
38	Correct	9 ms	4440 KB	Output is correct
39	Correct	8 ms	4640 KB	Output is correct
40	Correct	7 ms	4444 KB	Output is correct
41	Correct	6 ms	4444 KB	Output is correct
42	Correct	7 ms	4444 KB	Output is correct
43	Correct	150 ms	11496 KB	Output is correct
44	Correct	260 ms	11620 KB	Output is correct
45	Correct	246 ms	11640 KB	Output is correct
46	Correct	270 ms	11496 KB	Output is correct
47	Correct	170 ms	11700 KB	Output is correct
48	Correct	244 ms	11704 KB	Output is correct
49	Correct	254 ms	11892 KB	Output is correct
50	Correct	236 ms	11644 KB	Output is correct
51	Correct	246 ms	11640 KB	Output is correct
52	Correct	245 ms	11704 KB	Output is correct
53	Correct	260 ms	11708 KB	Output is correct
54	Correct	245 ms	11496 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4444 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4440 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	1 ms	4444 KB	Output is correct
18	Correct	1 ms	4696 KB	Output is correct
19	Correct	1 ms	4444 KB	Output is correct
20	Correct	1 ms	4440 KB	Output is correct
21	Correct	1 ms	4444 KB	Output is correct
22	Correct	1 ms	4444 KB	Output is correct
23	Correct	1 ms	4444 KB	Output is correct
24	Correct	1 ms	4444 KB	Output is correct
25	Correct	1 ms	4444 KB	Output is correct
26	Correct	1 ms	4444 KB	Output is correct
27	Correct	1 ms	4444 KB	Output is correct
28	Correct	1 ms	4444 KB	Output is correct
29	Correct	8 ms	4444 KB	Output is correct
30	Correct	9 ms	4444 KB	Output is correct
31	Correct	9 ms	4664 KB	Output is correct
32	Correct	8 ms	4664 KB	Output is correct
33	Correct	7 ms	4444 KB	Output is correct
34	Correct	8 ms	4444 KB	Output is correct
35	Correct	9 ms	4440 KB	Output is correct
36	Correct	9 ms	4444 KB	Output is correct
37	Correct	9 ms	4664 KB	Output is correct
38	Correct	9 ms	4440 KB	Output is correct
39	Correct	8 ms	4640 KB	Output is correct
40	Correct	7 ms	4444 KB	Output is correct
41	Correct	6 ms	4444 KB	Output is correct
42	Correct	7 ms	4444 KB	Output is correct
43	Correct	150 ms	11496 KB	Output is correct
44	Correct	260 ms	11620 KB	Output is correct
45	Correct	246 ms	11640 KB	Output is correct
46	Correct	270 ms	11496 KB	Output is correct
47	Correct	170 ms	11700 KB	Output is correct
48	Correct	244 ms	11704 KB	Output is correct
49	Correct	254 ms	11892 KB	Output is correct
50	Correct	236 ms	11644 KB	Output is correct
51	Correct	246 ms	11640 KB	Output is correct
52	Correct	245 ms	11704 KB	Output is correct
53	Correct	260 ms	11708 KB	Output is correct
54	Correct	245 ms	11496 KB	Output is correct
55	Correct	1953 ms	29964 KB	Output is correct
56	Correct	3336 ms	36336 KB	Output is correct
57	Correct	3225 ms	36000 KB	Output is correct
58	Correct	3475 ms	34044 KB	Output is correct
59	Correct	2383 ms	36668 KB	Output is correct
60	Correct	3523 ms	36664 KB	Output is correct
61	Correct	3442 ms	36664 KB	Output is correct
62	Correct	3204 ms	35888 KB	Output is correct
63	Correct	3157 ms	35828 KB	Output is correct
64	Correct	3651 ms	36592 KB	Output is correct
65	Correct	3581 ms	36592 KB	Output is correct
66	Correct	3219 ms	35900 KB	Output is correct
67	Correct	3517 ms	36596 KB	Output is correct

답안 #855340

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 21.0 / 21.0

Subtask #4 26.0 / 26.0

Subtask #5 13.0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
21.0 / 21.0

Subtask #4
26.0 / 26.0

Subtask #5
13.0 / 13.0