Submission #954357

#	Time	Username	Problem	Language	Result	Execution time	Memory
954357		LCJLY	Building 4 (JOI20_building4)	C++14	11 / 100	586 ms	346672 KiB

building4

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
int n;
int a[1000005];
int b[1000005];
int memo[4005][2005][2];
array<int,3>pp[4005][4005][2];

//a is true, b is false

int dp(int index, int take, bool amos){
	if(index==2*n){
		if(take==n){
			return true;
		}
		else return false;
	}
	if(memo[index][take][amos]!=-1) return memo[index][take][amos];
	bool ans=false;
	if(index==0){
		bool hold=dp(index+1,take+1,true);
		if(hold) pp[index][take][amos]={index+1,take+1,true};
		ans|=hold;
		
		hold=dp(index+1,take,false);
		if(hold) pp[index][take][amos]={index+1,take,false};
		ans|=hold;
	}
	else if(amos){
		if(a[index]>=a[index-1]){
			//ans|=dp(index+1,take+1,true);
			bool hold=dp(index+1,take+1,true);
			if(hold) pp[index][take][amos]={index+1,take+1,true};
			ans|=hold;
		}
		if(b[index]>=a[index-1]){
			//ans|=dp(index+1,take,false);
			bool hold=dp(index+1,take,false);
			if(hold) pp[index][take][amos]={index+1,take,false};
			ans|=hold;
		}
	}
	else{
		if(a[index]>=b[index-1]){
			//ans|=dp(index+1,take+1,true);
			bool hold=dp(index+1,take+1,true);
			if(hold) pp[index][take][amos]={index+1,take+1,true};
			ans|=hold;
		}
		if(b[index]>=b[index-1]){
			//ans|=dp(index+1,take,false);
			bool hold=dp(index+1,take,false);
			if(hold) pp[index][take][amos]={index+1,take,false};
			ans|=hold;
		}
	}
	return memo[index][take][amos]=(int)ans;
}
 
void solve(){
	cin >> n;
	
	for(int x=0;x<2*n;x++){
		cin >> a[x];
	}
	
	for(int x=0;x<2*n;x++){
		cin >> b[x];
	}
	
	memset(memo,-1,sizeof(memo));
	bool hold=dp(0,0,0);
	if(!hold){
		cout << -1;
		return;
	}
	
	array<int,3>cur;
	cur={0,0,0};
	
	while(cur[0]<2*n){
		array<int,3>nxt=pp[cur[0]][cur[1]][cur[2]];
		if(nxt[2]==1){
			cout << "A";
		}
		else cout << "B";
		cur=nxt;
	}
}	
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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