제출 #524053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524053		tube5429	San (COCI17_san)	C++14	120 / 120	115 ms	7576 KiB

san

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

#define sz(v) (int)(v).size()

typedef long long ll;
const int MX = 42;

int N, h[MX], g[MX];
ll K;

vector<int> hs;
vector<ll> L[MX], R[MX];
void rec_left(int pos, int last, ll sum) {
	if(pos == N/2) {
		int idx = lower_bound(hs.begin(), hs.end(), last) - hs.begin();
		L[idx].push_back(sum);
		return;
	}
	rec_left(pos+1, last, sum);
	if(h[pos] >= last) {
		rec_left(pos+1, h[pos], sum + g[pos]);
	}
}

void rec_right(int pos, int first, int last, ll sum) {
	if(pos == N) {
		int idx = lower_bound(hs.begin(), hs.end(), first) - hs.begin();
		R[idx].push_back(sum);
		return;
	}
	rec_right(pos+1, first, last, sum);
	if(h[pos] >= last) {
		int nfirst = (first == 0) ? h[pos] : first;
		rec_right(pos+1, nfirst, h[pos], sum + g[pos]);
	}
}

int main() {
	cin>>N>>K;
	for(int i = 0 ; i<N ; i++) {
		cin>>h[i]>>g[i];
		hs.push_back(h[i]);
	}
	hs.push_back(0);
	sort(hs.begin(), hs.end());
	rec_left(0, 0, 0);
	rec_right(N/2, 0, 0, 0);
	ll ans = 0;
	for(int i = 0; i<sz(hs) ; i++) {
		sort(R[i].begin(), R[i].end());
	}
	for(int i = 0 ; i<sz(hs) ; i++) {
		for(auto it : L[i]) {
			ans += R[0].end() - lower_bound(R[0].begin(), R[0].end(), K - it);
			for(int j = i; j<sz(hs); j++) {
				ans += R[j].end() - lower_bound(R[j].begin(), R[j].end(), K - it);
			}
		}
	}
	cout << ans << "\n";

	return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24