Submission #1186648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186648		NAMIN	Building 4 (JOI20_building4)	C++20	100 / 100	563 ms	71864 KiB

building4

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

const int mxN = 500001;
int N;
int dp[2*mxN][2][2];
vector<int> A,B;
//dp[i][j][k] = max(#times reach k ending at (i,j))

void calc(int i,int j,int cntA,int cntB){
	//cout << cntA << ' ' << cntB << endl;
	if(i == 0){
		if(j == 0)
			cout << 'A';
		else
			cout << 'B';
		return;
	}
	
	if(j == 0){
		if(A[i-1] <= A[i] && dp[i-1][0][0] >= cntA-1 && dp[i-1][0][1] >= cntB){
			calc(i-1,0,cntA-1,cntB);
		}
		else if(B[i-1] <= A[i] && dp[i-1][1][0] >= cntA-1 && dp[i-1][1][1] >= cntB){
			calc(i-1,1,cntA-1,cntB);
		}
	}
	else{//j == 1
		if(A[i-1] <= B[i] && dp[i-1][0][0] >= cntA && dp[i-1][0][1] >= cntB-1){
			calc(i-1,0,cntA,cntB-1);
		}
		else if(B[i-1] <= B[i] && dp[i-1][1][0] >= cntA && dp[i-1][1][1] >= cntB-1){
			calc(i-1,1,cntA,cntB-1);
		}
	}
	if(j == 0)
		cout << 'A';
	else
		cout << 'B';
}

int main(){
	cin >> N;
	A.resize(2*N),B.resize(2*N);
	memset(dp,0,sizeof(dp));
	for(int i=0;i<2*N;i++)
		cin >> A[i];
	for(int i=0;i<2*N;i++)
		cin >> B[i];
	
	dp[0][0][0] = 1;
	dp[0][1][1] = 1;
	for(int k=0;k<2;k++){
		for(int i=1;i<2*N;i++){
			for(int j=0;j<2;j++){
				if(j == 0){
					if(A[i] >= A[i-1])
						dp[i][j][k] = max(dp[i][j][k],
											dp[i-1][j][k]+(j==k));
					if(A[i] >= B[i-1])
						dp[i][j][k] = max(dp[i][j][k],
											dp[i-1][!j][k]+(j==k));
				}
				else{
					if(B[i] >= A[i-1])
						dp[i][j][k] = max(dp[i][j][k],
											dp[i-1][!j][k]+(j==k));
					if(B[i] >= B[i-1])
						dp[i][j][k] = max(dp[i][j][k],
											dp[i-1][j][k]+(j==k));
				}
			}
		}
	}

	if(dp[2*N-1][0][0] >= N && dp[2*N-1][0][1] >= N){
		calc(2*N-1,0,N,N);
	}
	else if(dp[2*N-1][1][0] >= N && dp[2*N-1][1][1] >= N){
		calc(2*N-1,1,N,N);
	}
	else
		cout << -1;
	cout << endl;
}

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