Submission #1032815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032815		Unforgettablepl	Chorus (JOI23_chorus)	C++17	61 / 100	7057 ms	4056 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int INF = 1e13;
 
struct fenwick{
	vector<int> tree;
	int n;
	fenwick(int n):n(n),tree(n+1){}
	void add(int k,int x){
		while(k<=n){
			tree[k]+=x;
			k+=k&-k;
		}
	}
	int get(int k){
		int ans = 0;
		while(k){
			ans+=tree[k];
			k-=k&-k;
		}
		return ans;
	}
};
 
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	s.insert(s.begin(),'$');
	vector<int> posA(n+1);
	vector<int> posB(n+1);
	int cntA = 0,cntB = 0;
	for(int i=1;i<=2*n;i++){
		if(s[i]=='A'){
			posA[++cntA]=i;
		} else {
			posB[++cntB]=i;
		}
	}
	vector<int> costA(n+1);
	vector<int> costB(n+1);
	vector<int> lastB(n+1);
	{
		fenwick temp(2*n);
		for(int i=n;i;i--){
			temp.add(posB[i],1);
			costA[i] = temp.get(posA[i]);
		}
		for(int i=1;i<=n;i++)costA[i]+=costA[i-1];
	}
	{
		fenwick temp(2*n);
		for(int i=n;i;i--){
			costB[i] = n-i-temp.get(posB[i]);
			temp.add(posA[i],1);
		}
		for(int i=1;i<=n;i++)costB[i]+=costB[i-1];
	}
	{
		int currlast = 0;
		for(int i=1;i<=n;i++){
			while(currlast!=n and posB[currlast+1]<posA[i])currlast++;
			lastB[i] = min(currlast,i);
		}
	}
	auto cost = [&](int a,int b){
		assert(a<=b);
		int Ac = costA[b]-costA[a-1];
		if(lastB[b]<a)return Ac;
		int amt = lastB[b]-a+1;;
		int Bc = costB[lastB[b]]-costB[a-1]-amt*(n-b);
		return Ac+Bc;
	};
	auto solve = [&](int penalty){
		vector<pair<int,int>> DP(n+1,{INF,INF});
		DP[0]={0,0};
		for(int i=1;i<=n;i++){
			for(int j=i;j;j--){
				DP[i]=min(DP[i],{DP[j-1].first+cost(j,i)+penalty,DP[j-1].second+1});
			}
		}
		return DP[n];
	};
	int best_penalty = -1;
	for(int jump=(1ll<<40);jump;jump/=2ll){
		if(solve(best_penalty+jump).second>k)best_penalty+=jump;
	}
	best_penalty++;
	cout << solve(best_penalty).first-k*best_penalty << '\n';
}

Compilation message (stderr)

chorus.cpp: In constructor 'fenwick::fenwick(long long int)':
chorus.cpp:10:6: warning: 'fenwick::n' will be initialized after [-Wreorder]
   10 |  int n;
      |      ^
chorus.cpp:9:14: warning:   'std::vector<long long int> fenwick::tree' [-Wreorder]
    9 |  vector<int> tree;
      |              ^~~~
chorus.cpp:11:2: warning:   when initialized here [-Wreorder]
   11 |  fenwick(int n):n(n),tree(n+1){}
      |  ^~~~~~~

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