Submission #756931

#	Time	Username	Problem	Language	Result	Execution time	Memory
756931		Dan4Life	Building 4 (JOI20_building4)	C++17	0 / 100	28 ms	16036 KiB

building4

#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)2e3+10;
int n, a[2][mxN*2];
bool dp[mxN][mxN][2];
 
int main(){
    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];
    dp[1][0][0]=dp[1][1][1] = 1;
    for(int i = 2; i <= 2*n; i++)
        for(int j = 0; j <= n; j++)
            for(int k = 0; k < 2; k++)
                for(int l = 0; l < 2; l++)
                    if(a[l][i-1]<=a[k][i] and j>=!!k) 
                        dp[i][j][k]|=dp[i-1][j-!!k][l];
    int tot = n, p=(int)1e9+10; string ans = "";
    for(int i = 2*n; i; i--){
        for(int k = 0; k < 2; k++){
            if(dp[i][tot][k] and a[k][i]<=p){
                tot-=!!k; ans+=(k?'B':'A'); p=a[k][i]; break;
            }
        }
        if(i==2*n and ans.empty()){cout<<-1;return 0;}
    }
    reverse(begin(ans),end(ans)); cout << ans << "\n";
}

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