Submission #413928

#	Time	Username	Problem	Language	Result	Execution time	Memory
413928		NintsiChkhaidze	Building 4 (JOI20_building4)	C++14	11 / 100	314 ms	376820 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<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<int,pair<int,int> > em = {0,{0,2*1e9}};
    for (int i=0;i<=2*n;i++)
        for (int j=0;j<=2*n;j++)
            dp[i][j] = em;
            
    dp[1][0] = {1,{1,A[1]}};
    dp[0][1] = {1,{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] && A[i] < dp[a+1][b].s.s)
                dp[a+1][b] = {i,{1,A[i]}};
                
            if (dp[a][b].s.s <= B[i] && B[i] < dp[a][b+1].s.s)
                dp[a][b+1] = {i,{2,B[i]}};
        }
    }
    
    if (dp[n][n].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: 11 / 11
• Subtask 2: 0 / 89