Submission #1130473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130473		Math4Life2020	Chorus (JOI23_chorus)	C++20	100 / 100	5493 ms	106872 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 = 1e18;
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;
	}
}

deque<pair<pii,ll>> chull; //{{slope,value},#}
//more negative slope at back
//answer queries at front

pii eval(pair<pii,ll> A0, ll x) {
	return {A0.first.first*x+A0.first.second,A0.second};
}

pii qryH(ll x) {
	pii pf = {INF,INF};
	if (chull.empty()) {
		return pf;
	}
	while(chull.size()>=2) {
		auto at = chull.front(); chull.pop_front();
		auto bt = chull.front();
		pii va = eval(at,x); pii vb = eval(bt,x);
		if (vb.first<va.first || ((vb.first==va.first)&&(vb.second<=va.second))) {
			//cout << "deleting at = "<<at.first.first<<","<<at.first.second<<","<<at.second<<"\n";
		} else {
			chull.push_front(at); 
			//assert(va==pf);
			return va;
		}
	}
	assert(chull.size()==1);
	auto at = chull.front();
	return eval(at,x);
}

bool isExtra(pii ap, pii bp, pii cp) {
	return (bp.first*(cp.second-ap.second)+bp.second*(ap.first-cp.first)>=ap.first*cp.second-ap.second*cp.first);
}

void insH(array<ll,3> A0) { //{value, slope, #}
	if (!chull.empty()) {
		auto at = chull.back();
		//assert(at.first.first>A0[1]);
	}
	chull.push_back({{A0[1],A0[0]},A0[2]});
	while (chull.size()>=3) {
		auto ct = chull.back(); chull.pop_back();
		auto bt = chull.back(); chull.pop_back();
		auto at = chull.back();
		if (isExtra(at.first,bt.first,ct.first)) {
			chull.push_back(ct);
			//cout << "deleting bt = "<<bt.first.first<<","<<bt.first.second<<","<<bt.second<<"\n";
		} else {
			chull.push_back(bt);
			chull.push_back(ct);
			return;
		}
	} 
}

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 << "process l="<<l<<"\n";
		// cout << "i0="<<io[l]<<"\n";
		for (auto A0: lns[l]) {
			//convex hull insert
			insH(A0); 
			//cout << "insert A0 = "<<A0[0]<<","<<A0[1]<<","<<A0[2]<<"\n";
		}
		pii qryV = qryH(l-1);
		//cout << "at value "<<(l-1)<<" qryV = "<<qryV.first<<","<<qryV.second<<"\n";
		dp[l]=fz(dp[l],qryV);
		//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) {
				insH(A0);
				//cout << "insert A0 = "<<A0[0]<<","<<A0[1]<<","<<A0[2]<<"\n";
			} 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<=0;q++) {
	// 	cout << "q="<<q<<"\n";
	// 	pii p0 = qry(q);
	// 	cout << "query value="<<p0.first<<","<<p0.second<<"\n";
	// }
	// exit(0);
	ll Cmin = 0; ll Cmax = N*N; //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: 26 / 26
• Subtask 5: 13 / 13