Submission #413912

#	Time	Username	Problem	Language	Result	Execution time	Memory
413912		NintsiChkhaidze	Building 4 (JOI20_building4)	C++14	0 / 100	280 ms	442588 KiB

building4

#include <bits/stdc++.h>
#define pb push_back
#define ll  long long
#define s second
#define f first
#define int ll
using namespace std;
const int N = 4005;
int A[N],B[N];
string s;
pair<pair<int,int>,pair<int,int> > dp[N][N]; 
main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n;
    cin>>n;
    
    for (int i=1;i<=2*n;i++) cin>>A[i];
    for (int i=1;i<=2*n;i++) cin>>B[i];
        
    pair<pair<int,int>,pair<int,int> > em = {{0,0},{0,0}};
    
    for (int i=0;i<=2*n;i++)
        for (int j=0;j<=2*n;j++)
            dp[i][j] = em;
            
    dp[1][0] = {{1,0},{1,A[1]}};
    dp[0][1] = {{1,0},{2,B[1]}};
    
    for (int i=2;i<=2*n;i++){
        for (int j=0;j<i;j++){
            int a=j,b = i - 1 - j;
            if (dp[a][b] == em) continue;
            if (dp[a][b].s.s <= A[i])
                dp[a + 1][b] = {{i,dp[a][b].f.f},{1,A[i]}};
            if (dp[a][b].s.s <= B[i])
                dp[a][b+1] = {{i,dp[a][b].f.f},{2,B[i]}};
        }
    }
    
    if (dp[n][n].f.f == 0) {
        cout<<-1;
        return 0;
    }
    int l=n,r=n;
    for (int i=2*n;i>=1;i--){
        if (dp[l][r].s.f == 2) s[i] = 'B',r--;
        else s[i] = 'A',l--;
    }
    for (int i=1;i<=2*n;i++)
        cout<<s[i];
}

Compilation message (stderr)

building4.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main (){
      | ^~~~

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