제출 #1214198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214198		emptypringlescan	Chorus (JOI23_chorus)	C++17	40 / 100	7122 ms	996676 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;
			}
		}
	}
	dp[0][0][0]=0;
	for(int i=0; i<=m; i++){
		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<m&&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]);
			}
		}
	}
	int ans=dp[m&1][n][2*n];
	//cout << ans << '\n';
	for(int i=n+1; i<2*n; i++){
		//cout << dp[m][i-n][i] << ' ' << cost[i+1][i-n+1][n] << '\n';
		ans=min(ans,dp[m&1][i-n][i]+cost[i+1][i-n+1][n]);
	}
	cout << ans;
}

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