Submission #598400

#	Time	Username	Problem	Language	Result	Execution time	Memory
598400		jk410	Building 4 (JOI20_building4)	C++17	11 / 100	208 ms	254436 KiB

building4

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
const int INF=1e9;
int N;
int A[4001],B[4001];
int DP[4001][4001][2];
string Ans;
int dp(int i,int j,int k){
    if (j<0)
        return 0;
    if (!i)
        return (!j);
    int &ret=DP[i][j][k];
    if (ret!=-1)
        return ret;
    if (k)
        return ret=(A[i-1]<=B[i]&&dp(i-1,j,0)||B[i-1]<=B[i]&&dp(i-1,j,1));
    return ret=(A[i-1]<=A[i]&&dp(i-1,j-1,0)||B[i-1]<=A[i]&&dp(i-1,j-1,1));
}
void solve(int i,int j,int k){
    if (!i)
        return;
    if (k){
        Ans+='B';
        if (A[i-1]<=B[i]&&dp(i-1,j,0))
            solve(i-1,j,0);
        else
            solve(i-1,j,1);
    }
    else{
        Ans+='A';
        if (A[i-1]<=A[i]&&dp(i-1,j-1,0))
            solve(i-1,j-1,0);
        else
            solve(i-1,j-1,1);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(DP,-1,sizeof(DP));
    cin>>N;
    for (int i=1; i<=2*N; i++)
        cin>>A[i];
    for (int i=1; i<=2*N; i++)
        cin>>B[i];
    if (dp(2*N,N,0)){
        solve(2*N,N,0);
        reverse(all(Ans));
        cout<<Ans;
        return 0;
    }
    if (dp(2*N,N,1)){
        solve(2*N,N,1);
        reverse(all(Ans));
        cout<<Ans;
        return 0;
    }
    cout<<"-1";
    return 0;
}

Compilation message (stderr)

building4.cpp: In function 'int dp(int, int, int)':
building4.cpp:19:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   19 |         return ret=(A[i-1]<=B[i]&&dp(i-1,j,0)||B[i-1]<=B[i]&&dp(i-1,j,1));
      |                     ~~~~~~~~~~~~^~~~~~~~~~~~~
building4.cpp:20:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |     return ret=(A[i-1]<=A[i]&&dp(i-1,j-1,0)||B[i-1]<=A[i]&&dp(i-1,j-1,1));
      |                 ~~~~~~~~~~~~^~~~~~~~~~~~~~~

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