제출 #1256070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256070		minhpk	Building 4 (JOI20_building4)	C++20	100 / 100	170 ms	49520 KiB

building4

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int z[1000005];
int t[1000005];
pair<int,int> dp[1000005][2];
int inf=1e16;
pair<int,int> combine(pair<int,int> a,pair<int,int> b,int add){
     return  make_pair(min(a.first,b.first+add),max(a.second,b.second+add));
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    int n=2*a;
    for (int i=1;i<=n;i++){
         cin >> z[i];
    }
    for (int i=1;i<=n;i++){
         cin >> t[i];
    }
    for  (int i=1;i<=n;i++){
         for (int j=0;j<=1;j++){
              dp[i][j]={inf,-inf};
         }
    }
    dp[1][0]={1,1};
    dp[1][1]={0,0};
    for (int i=2;i<=n;i++){
         if (z[i]>=z[i-1]){
             dp[i][0]=combine(dp[i][0],dp[i-1][0],1);
         }
         if (z[i]>=t[i-1]){
             dp[i][0]=combine(dp[i][0],dp[i-1][1],1);
         }
         if (t[i]>=z[i-1]){
             dp[i][1]=combine(dp[i][1],dp[i-1][0],0);
         }
         if (t[i]>=t[i-1]){
             dp[i][1]=combine(dp[i][1],dp[i-1][1],0);
         }
    }
    int prv=inf;
    int cnt=a;
    vector<char> c;
    for (int i=n;i>=1;i--){
         if (dp[i][0].first<=cnt && cnt<= dp[i][0].second && z[i]<=prv){
             c.push_back('A');
             cnt--;
             prv=z[i];
         }else if (dp[i][1].first<=cnt && cnt<= dp[i][1].second && t[i]<=prv){
             c.push_back('B');
             prv=t[i];
         }else{
             cout << -1 << "\n";
             return 0;
         }
    }
    while (c.size()){
         cout << c.back();
         c.pop_back();
    }
    return 0;
}

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