Submission #1214240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214240		emptypringlescan	Chorus (JOI23_chorus)	C++17	16 / 100	86 ms	132424 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
int dp[2][505][1005];
int n,m;
string s;
int cost[1005][505][505];
int ones[505];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	for(int i=0; i<2; i++) for(int j=0; j<505; j++) for(int k=0; k<1005; k++) dp[i][j][k]=1e8;
	cin >> n >> m;
	cin >> s;
	int cnt=1;
	for(int i=1; i<=2*n; i++){
		if(s[i-1]=='B'){
			ones[cnt]=i;
			cnt++;
		}
	}
	for(int i=1; i<=2*n; i++){
		for(int j=1; j<=n; j++){
			int cur=0;
			for(int k=j; k<=n; k++){
				cur+=(ones[k]>=i+k-j?0:i+k-j-ones[k]);
				cost[i][j][k]=cur;
			}
		}
	}
	vector<int> ansers;
	dp[0][0][0]=0;
	for(int i=0; i<=n; i++){
		for(int j=0; j<=n; j++){
			for(int k=0; k<=n*2; k++){
				dp[!(i&1)][j][k]=1e8;
			}
		}
		for(int j=0; j<=n; j++){
			for(int k=ones[j]; k<=n*2; k++){
				if(k+1<=2*n&&i) dp[i&1][j][k+1]=min(dp[i&1][j][k+1],dp[i&1][j][k]+1);
				if(i<n&&k-j+1<=n&&k+k-2*j+1<=2*n&&k-j+1>j) dp[!(i&1)][k-j+1][max(ones[k-j+1],k+k-2*j+1)]=min(dp[!(i&1)][k-j+1][max(ones[k-j+1],k+k-2*j+1)],dp[i&1][j][k]+cost[k+1][j+1][k-j+1]);
			}
		}
		if(i){
			int ans=dp[i&1][n][2*n];
			//cout << ans << '\n';
			for(int j=n+1; j<2*n; j++){
				//cout << dp[m][i-n][i] << ' ' << cost[i+1][i-n+1][n] << '\n';
				ans=min(ans,dp[i&1][j-n][j]+cost[j+1][j-n+1][n]);
			}
			if(ans<1e8) ansers.push_back(ans);
		}
		
	}
	//for(int i:ansers) cout << i << ' ';
	//cout << ans << '\n';
	for(int i=1; i<(int)ansers.size()-1; i++){
		assert(ansers[i-1]-ansers[i]>=ansers[i]-ansers[i+1]);
	}
	cout << ansers[m-1];
}

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