Submission #834722

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
834722	2023-08-22T17:44:25 Z	Antekb	Chorus (JOI23_chorus)	C++17	16 / 100	17 ms	468 KB

chorus

#include<bits/stdc++.h>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
using ld = long double;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t)){
		cerr<<", ";
	}
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main(){
	int n, k;
	string s;
	cin>>n>>k>>s;
	vi V(n+1);
	int a=0, b=1;
	for(char c:s){
		if(c=='A'){
			a++;
		}
		else{
			V[b]=a;
			b++;
		}
	}
	/*vector<vector<ll> > dp2(n+1, vector<ll>(k+1, 1e18));
	dp2[0][0]=0;
	for(int kk=1; kk<=k; kk++){
		for(int i=kk; i<=n; i++){
			ll c=0;
			for(int j=i-1; j>=0; j--){
				c+=max(0, i-V[j+1]);
				dp2[i][kk]=min(dp2[i][kk], dp2[j][kk-1]+c);
			}
		}
	}
	for(int kk=1; kk<=k; kk++){
		cout<<dp2[n][kk]<<" ";
	}*/
	vector<ld> dp(n+1), ile(n+1);
	ld l=-2e7, r=2e7;
	pair<int, ll> L,R;
	for(int ii=0; ii<30; ii++){
		ld m=(l+r)/2;
		dp[0]=0;
		ile[0]=0;
		for(int i=1; i<=n; i++){
			ll c=0;
			dp[i]=1e18;
			for(int j=i-1; j>=0; j--){
				c+=max(0, i-V[j+1]);
				if(dp[i]>dp[j]+c+m){
					dp[i]=dp[j]+c+m;
					ile[i]=ile[j]+1;
				}
			}
		}
		if(ile[n]>k){
			l=m;
			R=mp(ile[n], ll(dp[n]-k*m+0.5));
		}
		else if(ile[n]<k){
			r=m;
			L=mp(ile[n], ll(dp[n]-k*m+0.5));
		}
		else{
			cout<<ll(dp[n]-k*m+0.5);
			return 0;
		}
	}
	assert((R.nd*(k-L.st)+L.nd*(R.st-k))%(R.st-L.st)==0);
	ll ans=(R.nd*(k-L.st)+L.nd*(R.st-k))/(R.st-L.st);
	cout<<ans;
	//assert(false);
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 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	0 ms	212 KB	Output is correct
10	Correct	0 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	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct

Subtask #2

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 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	0 ms	212 KB	Output is correct
10	Correct	0 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	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	3 ms	212 KB	Output is correct
18	Runtime error	17 ms	468 KB	Execution killed with signal 6
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 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	0 ms	212 KB	Output is correct
10	Correct	0 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	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	3 ms	212 KB	Output is correct
18	Runtime error	17 ms	468 KB	Execution killed with signal 6
19	Halted	0 ms	0 KB	-

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 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	0 ms	212 KB	Output is correct
10	Correct	0 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	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	3 ms	212 KB	Output is correct
18	Runtime error	17 ms	468 KB	Execution killed with signal 6
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 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	0 ms	212 KB	Output is correct
10	Correct	0 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	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	3 ms	212 KB	Output is correct
18	Runtime error	17 ms	468 KB	Execution killed with signal 6
19	Halted	0 ms	0 KB	-