Submission #211910

#	Time	Username	Problem	Language	Result	Execution time	Memory
211910		peijar	Building 4 (JOI20_building4)	C++17	100 / 100	372 ms	24952 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define SZ(x) ((int)(x).size())

typedef	long long ll;

const int INF = 1e6;

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

	vector<array<int, 2>> cost(2*n);

	for (int j(0); j < 2; ++j)
		for (int i(0); i < 2*n; ++i)
			cin >> cost[i][j];

	vector<array<int, 2>> lft(2*n);
	vector<array<int, 2> > rght(2*n);

	lft[2*n-1][0] = rght[2*n-1][0] = 0;
	lft[2*n-1][1] = rght[2*n-1][1] = 1;
	for (int i(2*n-2); i >= 0; --i)
	{
		for (int c(0); c < 2; ++c)
		{
			lft[i][c] = lft[i][c] = INF;
			rght[i][c] = rght[i][c] = -1;
			for (int d(0); d < 2; ++d)
				if (cost[i][c] <= cost[i+1][d] and lft[i+1][d] != INF)
				{
					lft[i][c] = min(lft[i][c], c + lft[i+1][d]);
					rght[i][c] = max(rght[i][c], c + rght[i+1][d]);
				}
		}
	}

	string colors = "AB";

	for (int start_col(0); start_col < 2; ++start_col)
	{
		if (lft[0][start_col] <= n and rght[0][start_col] >= n)
		{
			int cur_col = start_col;
			int want = n - start_col;
			for (int i(0); i < 2*n-1; ++i)
			{
				cout << colors[cur_col];
				for (int nxt_col(0); nxt_col < 2; ++nxt_col)
					if (cost[i][cur_col] <= cost[i+1][nxt_col]
						and lft[i+1][nxt_col] <= want
						and rght[i+1][nxt_col] >= want)
					{
						cur_col = nxt_col;
						want -= cur_col;
						break;
					}
			}
			cout << colors[cur_col] << endl;
			return 0;
		}
	}

	cout << -1 << endl;
}

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