제출 #1170966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170966		laure	건물 4 (JOI20_building4)	C++20	11 / 100	368 ms	589824 KiB

building4

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    n*=2;
    vector<int>a(n+1,0),b(n+1,0);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    int dp[n+1][n/2+1][2];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n/2;j++)
        {
            dp[i][j][0]=0;
            dp[i][j][1]=0;
        }
    }
    dp[0][0][0]=1;
    dp[0][0][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=max(0ll,i-(n/2));j<=min(i,n/2);j++)
        {
            if(j>0)dp[i][j][0]=(a[i-1]<=a[i]&&dp[i-1][j-1][0])||(b[i-1]<=a[i]&&dp[i-1][j-1][1]);
            if(j<i)dp[i][j][1]=(a[i-1]<=b[i]&&dp[i-1][j][0])||(b[i-1]<=b[i]&&dp[i-1][j][1]);
        }
    }
    if(dp[n][n/2][0]==0&&dp[n][n/2][1]==0)
    {
        cout<<-1<<'\n';
        return 0;
    }
    int i=n,k,j=n/2;
    vector<char>s;
    if(dp[i][j][0]){k=0;s.push_back('A');}
    else {k=1;s.push_back('B');}
    while(i>1)
    {
        if(!k)
        {
            if(b[i-1]<=a[i]&&dp[i-1][j-1][1])k=1;
            j--;
        }
        else
        {
            if(a[i-1]<=b[i]&&dp[i-1][j][0])k=0;
        }
        if(k)s.push_back('B');
        else {s.push_back('A');}
        i--;
    }
    reverse(s.begin(),s.end());
    for(auto u:s)cout<<u;
}

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