제출 #1044546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044546		earlyamazon	Port Facility (JOI17_port_facility)	C++14	10 / 100	231 ms	596 KiB

port_facility

// n <= 20

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

int n;
vector<pair<int,int>> t;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for (int i = 0; i < n; i++){
		int a,b;
		cin>>a>>b;
		t.push_back({a,b});
	}
	sort(t.begin(), t.end());
	int w = 0;
	if (n > 20){
		cout<<w<<"\n";
		return 0;
	}
	for (int i = 0; i < (1<<n); i++){
		vector<int> st1 = {2*n+1}, st2 = {2*n+1};
		bool ok = 1;
		for (int j = 0; j < n; j++){
			while (st1.back() < t[j].first) st1.pop_back();
			while (st2.back() < t[j].first) st2.pop_back();
			if ((1<<j) & i){
				if (t[j].second > st1.back()) ok = 0;
				st1.push_back(t[j].second);
			}
			else{
				if (t[j].second > st2.back()) ok = 0;
				st2.push_back(t[j].second);
			}
		}
		if (ok) w++;
	}
	cout<<w<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22