Submission #378457

#	Time	Username	Problem	Language	Result	Execution time	Memory
378457		eulerdesoja	Building 4 (JOI20_building4)	C++14	11 / 100	125 ms	32384 KiB

building4

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

#define ll long long
#define pb push_back
#define sz(x) int(x.size())

typedef pair<int,int>ii;
typedef vector<int> vi;

const int mxn=2e3+5;
int n,a[2][2*mxn];
int dp[mxn][mxn][2];
vector<char>ans(2*n+1);

int solve(int i,int j,int k){
	if(dp[i][j][k]!=-1)return dp[i][j][k];
	if(i>n || j>n)return 0;
	if(i+j==2*n){
		if(i==n && j==n){
			if(ans[i+j]=='$')ans[i+j]=(k==0?'A':'B');
			return 1;
		}
		return 0;
	}

	int id=i+j;
	int  ok=0;
	if(a[0][id+1]>=a[k][id] && i+1<=n)ok|=solve(i+1,j,0);
	if(a[1][id+1]>=a[k][id] && j+1<=n)ok|=solve(i,j+1,1);

	if(ok && ans[i+j]=='$')ans[i+j]=(k==0?'A':'B');

	return dp[i][j][k]=ok;

}


int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);

	//setIO("sort");
	cin>>n;
	for(int i=1;i<=2*n;i++)cin>>a[0][i];
	for(int i=1;i<=2*n;i++)cin>>a[1][i];
	memset(dp,-1,sizeof(dp));
	/*for(int sum=0;sum<2*n;sum++){
		for(int j=0;j<=sum;j++){
			int i=sum-j;
			for(int k=0;k<2;k++){
				if(!dp[i][j][k])continue;
				if(a[0][sum+1]>=a[k][sum] && i+1<=n)dp[i+1][j][0]=1;
				if(a[1][sum+1]>=a[k][sum] && j+1<=n)dp[i][j+1][1]=1;
			}

		}
	}*/
	for(int i=0;i<=2*n;i++)ans[i]='$';
	solve(0,0,0);
	solve(0,0,1);

	if(ans[1]=='$'){
		cout<<-1<<"\n";
		return 0;
	}
	for(int i=1;i<=2*n;i++)cout<<ans[i];
	cout<<"\n";
	return 0;
}

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