Submission #329377

#	Time	Username	Problem	Language	Result	Execution time	Memory
329377		limabeans	Building 4 (JOI20_building4)	C++17	100 / 100	319 ms	60140 KiB

building4

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 500001*2;
const int inf = 2e9;

int n;
int a[maxn][2];
int dpLow[maxn][2], dpHigh[maxn][2]; //range of # of B's


void setMin(int &x, int y) {
    x = min(x, y);
}

void setMax(int &x, int y) {
    x = max(x, y);
}


bool solve(int i, int b, int hi) {
    if (i==-1) {
	return true;
    }
    if (a[i][0]<=hi && dpLow[i][0]<=b && b<=dpHigh[i][0]) {
	solve(i-1,b,a[i][0]);
	cout<<"A";
	return true;
    }

    if (a[i][1]<=hi && b>0 && dpLow[i][1]<=b && b<=dpHigh[i][1]) {
	solve(i-1,b-1,a[i][1]);
	cout<<"B";
	return true;
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    n *= 2;
    for (int j=0; j<2; j++) {
	for (int i=0; i<n; i++) {
	    cin>>a[i][j];
	}
    }


    for (int i=0; i<n; i++) {
	for (int j=0; j<2; j++) {
	    dpLow[i][j] = inf;
	    dpHigh[i][j] = -inf;
	}
    }


    dpLow[0][0] = dpHigh[0][0] = 0;
    dpLow[0][1] = dpHigh[0][1] = 1;

    for (int i=0; i<n-1; i++) {
	for (int j=0; j<2; j++) {
	    
	    if (a[i][j] <= a[i+1][0]) {
		setMin(dpLow[i+1][0], dpLow[i][j]);
		setMax(dpHigh[i+1][0], dpHigh[i][j]);
	    }
	    
	    if (a[i][j] <= a[i+1][1]) {
		setMin(dpLow[i+1][1], dpLow[i][j]+1);
		setMax(dpHigh[i+1][1], dpHigh[i][j]+1);
	    }
	}
    }


    if (!solve(n-1,n/2,inf)) {
	out(-1);
    }
    
    return 0;
}

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