Submission #1130463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130463		Math4Life2020	Chorus (JOI23_chorus)	C++20	61 / 100	7091 ms	7624 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 1e6+5; const ll INF = 1e9;
ll c[Nm];
ll psc[Nm+1];
ll io[Nm]; //first i with c[i0]-l>=0
ll N; 

pii fz(pii p1, pii p2) {
	if (p1.first<p2.first) {
		return p1; 
	}
	if (p1.first>p2.first) {
		return p2;
	}
	if (p1.second<p2.second) {
		return p1;
	} else {
		return p2;
	}
}

vector<array<ll,3>> chull;

pii qryH(ll x) {
	pii pf = {INF,INF};
	for (auto A0: chull) {
		pf = fz(pf,{A0[0]+A0[1]*x,A0[2]});
	}
	return pf;
}

pii qry(ll Ctest) {
	chull.clear();
	pii dp[N+1]; //{cost,# used}
	for (ll i=1;i<=N;i++) {
		dp[i]={INF,INF};
	}
	dp[0]={0,0};
	deque<pii> d0;
	vector<array<ll,3>> lns[N+1];
	for (ll l=0;l<=N;l++) {
		//process
		// cout << "\nprocess l="<<l<<"\n";
		// cout << "i0="<<io[l]<<"\n";
		for (auto A0: lns[l]) {
			chull.push_back(A0);
		}
		dp[l]=fz(dp[l],qryH(l-1));
		//cout << "dp[l]="<<dp[l].first<<","<<dp[l].second<<"\n";
		if (dp[l].first==INF) {
			continue;
		}
		if (io[l]==N) {
			dp[N]=fz(dp[N],{dp[l].first+Ctest,dp[l].second+1});
		} else {
			array<ll,3> A0 = {Ctest+dp[l].first+psc[l]-psc[io[l]]+l*(io[l]-1),-l,dp[l].second+1};
			//cout << "A0: "<<A0[0]<<","<<A0[1]<<","<<A0[2]<<"\n";
			//lns[io[l]].push_back({Ctest+dp[l].first+psc[l]-psc[io[l]]+l*(io[l]-1),-l,dp[l].second+1});
			if (io[l]==l) {
				chull.push_back(A0);
			} else {
				lns[io[l]].push_back(A0);
			}
		}
	}
	return {dp[N].first-dp[N].second*Ctest,dp[N].second};
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll K; cin >> N >> K;
	string s; cin >> s;
	ll i0 = 0; ll c0 = 0;
	psc[0]=0;
	for (ll i=0;i<(2*N);i++) {
		if (s[i]=='A') {
			c[i0]=c0; psc[i0+1]=psc[i0]+c[i0];
			//cout << "i0="<<i0<<", c[i0]="<<c[i0]<<"\n";
			i0++;
		} else {
			assert(s[i]=='B');
			c0++;
		}
	}
	ll iov = N;
	io[N]=N;
	for (ll l=(N-1);l>=0;l--) {
		while (iov>0 && (c[iov-1]>=l)) {
			iov--;
		}
		io[l]=max(l,iov);
	}
	// for (ll q=0;q<=25;q++) {
	// 	cout << "q="<<q<<"\n";
	// 	pii p0 = qry(q);
	// 	cout << "query value="<<p0.first<<","<<p0.second<<"\n";
	// }
	//exit(0);
	ll Cmin = 0; ll Cmax = INF/2; //aliens constant
	//binary search for the smallest C where you use
	//at most K blocks
	while (Cmin<Cmax) {
		ll Ctest = (Cmin+Cmax)/2;
		pii p0 = qry(Ctest); //{cost, # of blocks}
		if (p0.second<=K) {
			Cmax = Ctest;
		} else {
			Cmin = Ctest+1;
		}
	}
	pii p0 = qry(Cmin);
	assert(p0.second<=K);
	pii p1 = qry(Cmin-1); //lower cost, higher # of blocks
	if (p0.second==K || p0.second==p1.second) {
		cout << (p0.first+psc[N])<<"\n";
	} else {
		ll fv = p0.first-(K-p0.second)*(p0.first-p1.first)/(p1.second-p0.second);
		cout << (fv+psc[N]) <<"\n";
	}
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13