Submission #234924

#	Time	Username	Problem	Language	Result	Execution time	Memory
234924		AMO5	Building 4 (JOI20_building4)	C++17	11 / 100	433 ms	132472 KiB

building4

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int const mxn = 4044;
bool dp[mxn][mxn][2][2]; //pos, cnt of b, cur, last
int a[mxn],b[mxn];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n; cin >> n;
	memset(dp,false,sizeof(dp));
	for(int i=1; i<=n*2; i++)cin >> a[i];
	for(int i=1; i<=n*2; i++)cin >> b[i];
	dp[1][0][0][0] = 1;
	dp[1][1][1][0] = 1;
	for(int i=2; i<=n*2; i++){
		for(int j=0; j<i; j++){
			for(int k=0; k<2; k++){
				for(int l=0; l<2; l++){
					if(dp[i-1][j][k][l]){
						if(!k){
							if(a[i]>=a[i-1])dp[i][j][0][0]=1;
							if(b[i]>=a[i-1])dp[i][j+1][1][0]=1;
						}else{
							if(a[i]>=b[i-1])dp[i][j][0][1]=1;
							if(b[i]>=b[i-1])dp[i][j+1][1][1]=1;
						}
					}
				}
			}
		}
	}
	bool find=0,cur=0,last=0;
	for(int i=0; i<2&&!find; i++){
		for(int j=0; j<2&&!find; j++){
			if(dp[n*2][n][i][j]){
				cur = i;
				last = j;
				find = 1;
			}
		}
	}
	if(!find){
		cout << -1 << endl;
		return 0;
	}
	//start backtracking
	string s="";
	int ptr = 2*n, cnt = n;
	while(ptr!=0){
		if(!cur){
			s+="A";
			ptr--;
			cur = last;
			if(dp[ptr][cnt][cur][0])last = 0;
			else last = 1;
		}else{ 
			s+="B";
			ptr--;
			cnt--;
			cur = last;
			if(dp[ptr][cnt][cur][0])last = 0;
			else last = 1;
		}
	}
	reverse(all(s));
	cout << s << endl;
}	

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