Submission #1186357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186357		NAMIN	Building 4 (JOI20_building4)	C++20	11 / 100	2098 ms	63304 KiB

building4

#include <bits/stdc++.h>

#define endl "\n"
#define ll long long

using namespace std;

const int mxN = 2001;
int dp[2*mxN][2][mxN+1];
vector<int> A(2*mxN),B(2*mxN);
int N;

string res(int i,int j,int k){
	//cout << i << ' ' << j << ' ' << k << endl;
	if(i == 0){
		if(j == 0)
			return "A";
		else
			return "B";
	}

	if(j == 0){
		if(dp[i-1][0][k-1] && A[i-1] <= A[i]){
			return res(i-1,0,k-1)+'A';
		}
		else if(dp[i-1][1][k-1] && B[i-1] <= A[i]){
			return res(i-1,1,k-1)+'A';
		}
	}
	else{
		if(dp[i-1][0][k] && A[i-1] <= B[i]){
			return res(i-1,0,k)+'B';
		}
		else if(dp[i-1][1][k] && B[i-1] <= B[i]){
			return res(i-1,1,k)+'B';
		}
	}
	return "";
}

void solve(){
	cin >> N;
	for(int i=0;i<2*N;i++){
		cin >> A[i];
	}
	for(int i=0;i<2*N;i++)
		cin >> B[i];
	
	memset(dp,0,sizeof(dp));
	dp[0][0][1] = 1;
	dp[0][1][0] = 1;
	for(int i=1;i<2*N;i++){
		for(int j=0;j<=N;j++){
			if(j && A[i-1] <= A[i])
				dp[i][0][j] |= dp[i-1][0][j-1];
			if(j && B[i-1] <= A[i])
				dp[i][0][j] |= dp[i-1][1][j-1];

			if(B[i-1] <= B[i])
				dp[i][1][j] |= dp[i-1][1][j];
			if(A[i-1] <= B[i])
				dp[i][1][j] |= dp[i-1][0][j];
		}
	}
	
	/*for(int cnt=0;cnt <= N;cnt++){
		cout << "cnt : " << cnt << endl;
		for(int j=0;j<2;j++){
			for(int i=0;i<2*N;i++){
				cout << dp[i][j][cnt] << ' ';
			}
			cout << endl;
		}
		cout << endl;
	}*/

	if(dp[2*N-1][0][N]){
		//cout << res(2*N-2,0,N-1) << endl;
		string ans = res(2*N-1,0,N);
		//reverse(ans.begin(),ans.end());
		cout << ans << endl;
	}
	else if(dp[2*N-1][1][N]){
		//cout << 'B'+res(2*N-2,1,N) << endl;
		string ans = res(2*N-1,1,N);
		//reverse(ans.begin(),ans.end());
		cout << ans << endl;
	}
	else{
		cout << -1 << endl;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 89