Submission #253273

#	Time	Username	Problem	Language	Result	Execution time	Memory
253273		Lawliet	Building 4 (JOI20_building4)	C++17	100 / 100	487 ms	36728 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000010;
const int INF = 1000000010;

int n;

int v[MAXN][2];
int dp[MAXN][2];

void solveDP(int p)
{
	for(int i = 2*n ; i > 0 ; i--)
	{
		for(int j = 0 ; j < 2 ; j++)
		{
			dp[i][j] = -INF;

			for(int nxt = 0 ; nxt < 2 ; nxt++)
			{
				int curValue = dp[i + 1][nxt];
				if( nxt == p ) curValue++;

				if( v[i - 1][j] <= v[i][nxt] )
					dp[i][j] = max( dp[i][j] , curValue );
			}
		}
	}
}

int main()
{
	scanf("%d",&n);

	for(int k = 0 ; k < 2 ; k++)
		for(int i = 1 ; i <= 2*n ; i++)
			scanf("%d",&v[i][k]);

	for(int k = 1 ; k >= 0 ; k--)
	{
		solveDP( k );

		if( dp[1][0] < n )
		{
			printf("-1\n");
			return 0;
		}
	}

	int last = 0;
	int remainA = n;

	for(int i = 1 ; i <= 2*n ; i++)
	{
		if( dp[i + 1][1] >= remainA && v[i][1] >= last )
		{
			printf("B");
			last = v[i][1];
		}
		else
		{
			printf("A");

			remainA--;
			last = v[i][0];
		}
	}
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
building4.cpp:39:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&v[i][k]);
    ~~~~~^~~~~~~~~~~~~~~

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