Submission #344881

#	Time	Username	Problem	Language	Result	Execution time	Memory
344881		wwdd	Building 4 (JOI20_building4)	C++14	100 / 100	353 ms	79420 KiB

building4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 500500;
const ll INFL = 1e18;
typedef vector<ll> vl;
ll dp[2*MN][2][2];
vl w[2];
bool sur(int id, int pos, int val) {
	return dp[pos][id][0] <= val && dp[pos][id][1] >= val;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin >> n;
	for(int i=0;i<2;i++) {
		for(int j=0;j<2*n;j++) {
			ll t;
			cin >> t;
			w[i].push_back(t);
		}
	}
	dp[0][0][0] = dp[0][0][1] = 0;
	dp[0][1][0] = dp[0][1][1] = 1;
	for(int i=1;i<2*n;i++) {
		for(int j=0;j<2;j++) {
			dp[i][j][0] = INFL;
			dp[i][j][1] = -INFL;
			for(int k=0;k<2;k++) {
				if(w[k][i-1] <= w[j][i]) {
					dp[i][j][0] = min(dp[i-1][k][0]+j,dp[i][j][0]);
					dp[i][j][1] = max(dp[i-1][k][1]+j,dp[i][j][1]);
				}
			}
		}
	}
	int wid;
	bool poss = false;
	int rem = n;
	for(int i=0;i<2;i++) {
		if(sur(i,2*n-1,n)) {
			wid = i;poss = true;
		}
	}
	if(poss) {
	vl res;
	res.push_back(wid);
	rem -= wid;
	for(int i=2*n-1;i>0;i--) {
		int nid = -1;
		for(int j=0;j<2;j++) {
			if(w[j][i-1] <= w[wid][i] && sur(j,i-1,rem)) {
				nid = j;
			}
		}
		res.push_back(nid);
		rem -= nid;
		wid = nid;
	}
	reverse(res.begin(),res.end());
	for(int i=0;i<res.size();i++) {
		cout << char(res[i]+'A');
	}
	cout << '\n';
	} else {
		cout << -1 << '\n';
	}
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<res.size();i++) {
      |              ~^~~~~~~~~~~

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