Submission #378419

#	Time	Username	Problem	Language	Result	Execution time	Memory
378419		MatheusLealV	Building 4 (JOI20_building4)	C++17	11 / 100	1495 ms	207228 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(qb < 0) return 0;
	if(i > n) return (qb == 0);
	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;
	
	int r=-1,l=-1;
	for(int c = 1; c <= n; c++){
		if(solve(1,c,0)){
			r=c;
			if(l ==-1)l=c;
		}
	}
	for(int c=l;c<=r and l != -1 and r != -1;c++){
		assert(solve(1, c, 0) == 1);
	}
	if(solve(1,n/2,0))print(1,n/2,0,s),cout<<s<<"\n";
	else cout<<"-1\n";
	// cout<<solve(1,0,0)<<"\n";
}

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