Submission #378417

#	Time	Username	Problem	Language	Result	Execution time	Memory
378417		MatheusLealV	Building 4 (JOI20_building4)	C++17	11 / 100	663 ms	176968 KiB

building4

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define N 4050
int n;
char t[2]={'A','B'};
int dp[N][N][2], v[2][N], prox[N][N][2];
void print(int i, int qb, int flag,string &s){
	if(i>n)return;
	int c= prox[i][qb][flag];
	s.pb(t[c]);
	print(i+1,qb+c,c,s);
}
int solve(int i, int qb, int flag){
	if(i > n) return (qb == n/2);
	if(dp[i][qb][flag]!=-1)return dp[i][qb][flag];
	int ans=0;
	for(int c=0;c<2;c++)
		if(v[c][i]>=v[flag][i-1] and solve(i+1,qb+c,c)) ans = 1,prox[i][qb][flag]=c;

	return dp[i][qb][flag]=ans;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	if(n>3000)return 0;
	n *= 2;
	for(int i = 1; i <= n; i++) cin>>v[0][i];
	for(int i = 1; i <= n; i++) cin>>v[1][i];
	memset(dp,-1,sizeof dp);
	string s;
	if(solve(1,0,0))print(1,0,0,s),cout<<s<<"\n";
	else cout<<"-1\n";
	// cout<<solve(1,0,0)<<"\n";
}

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