Submission #1029817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029817		Unforgettablepl	Chorus (JOI23_chorus)	C++17	40 / 100	7034 ms	80212 KiB

chorus

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e12;

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<vector<int>> DP(n+1,vector<int>(k+1,INF));
	DP[0][0]=0;
	for(int i=1;i<=n;i++){
		fenwick addedA(2*n);
		fenwick addedB(2*n);
		int ans = 0;
		for(int j=i+1;j<=n;j++)addedB.add(posB[j],1);
		for(int j=i;j;j--){
			ans+=addedA.get(2*n)-addedA.get(posB[j]);
			addedB.add(posB[j],1);
			ans+=addedB.get(posA[j]);
			addedA.add(posA[j],1);
			for(int l=1;l<=k;l++){
				DP[i][l]=min(DP[i][l],DP[j-1][l-1]+ans);
			}
		}
	}
	cout << DP[n][k] << '\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: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13