Submission #1000613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000613		irmuun	Building 4 (JOI20_building4)	C++17	11 / 100	373 ms	524288 KiB

building4

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    ll a[2*n+5],b[2*n+5];
    for(ll i=1;i<=2*n;i++){
        cin>>a[i];
    }
    for(ll i=1;i<=2*n;i++){
        cin>>b[i];
    }
    bool dp[2*n+5][n+5][2];//current building, A's count,i-th building type
    memset(dp,false,sizeof dp);
    ll bef[2*n+5][n+5][2];
    memset(bef,-1,sizeof bef);
    dp[1][1][0]=true;
    dp[1][0][1]=true;
    for(ll i=2;i<=2*n;i++){
        for(ll j=0;j<=n;j++){
            ll A=j,B=i-1-j;
            if(A<0||B<0||A>n||B>n) continue;
            if(A<n){
                if(dp[i-1][A][0]==true&&a[i-1]<=a[i]){
                    dp[i][A+1][0]=true;
                    bef[i][A+1][0]=0;
                }
                if(dp[i-1][A][1]==true&&b[i-1]<=a[i]){
                    dp[i][A+1][0]=true;
                    bef[i][A+1][0]=1;
                }
            }
            if(B<n){
                if(dp[i-1][A][0]==true&&a[i-1]<=b[i]){
                    dp[i][A][1]=true;
                    bef[i][A][1]=0;
                }
                if(dp[i-1][A][1]==true&&b[i-1]<=b[i]){
                    dp[i][A][1]=true;
                    bef[i][A][1]=1;
                }
            }
        }
    }
    if(!dp[2*n][n][0]&&!dp[2*n][n][1]){
        cout<<-1;
        return 0;
    }
    string s="";
    ll pos=0,cnt=n;
    if(dp[2*n][n][1]){
        pos=1;
    }
    for(ll i=2*n;i>=1;i--){
        if(pos==0){
            s+='A';
        }
        else{
            s+='B';
        }
        ll p=pos;
        if(i>1){
            pos=bef[i][cnt][pos];
        }
        if(p==0) cnt--;
    }
    reverse(all(s));
    cout<<s;
}

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