Submission #404140

#	Time	Username	Problem	Language	Result	Execution time	Memory
404140		penguinhacker	San (COCI17_san)	C++14	120 / 120	58 ms	16792 KiB

san

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

#define ll long long
#define ar array

int n, a[40], b[40];
ll k, ans;
vector<ll> l, r, v[40], all;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i=0; i<n; ++i)
		cin >> a[i] >> b[i];
	int mid=(n-1)/2;
	for (int i=0; i<=mid; ++i) {
		l.push_back(i);
		v[i]={b[i]};
		for (int j=0; j<i; ++j)
			if (a[j]<=a[i])
				for (ll x : v[j])
					v[i].push_back(x+b[i]);
		sort(v[i].begin(), v[i].end());
		for (ll j : v[i])
			ans+=j>=k;
	}
	for (int i=n-1; i>mid; --i) {
		r.push_back(i);
		v[i]={b[i]};
		for (int j=i+1; j<n; ++j)
			if (a[i]<=a[j])
				for (ll x : v[j])
					v[i].push_back(x+b[i]);
		sort(v[i].begin(), v[i].end());
		for (ll j : v[i])
			ans+=j>=k;
	}
	sort(l.begin(), l.end(), [](int x, int y) {return a[x]>a[y];});
	sort(r.begin(), r.end(), [](int x, int y) {return a[x]<a[y];});
	for (int i : r) {
		while(!l.empty()&&a[l.back()]<=a[i]) {
			vector<ll>& c=v[l.back()];
			vector<ll> nxt(all.size()+c.size());
			merge(all.begin(), all.end(), c.begin(), c.end(), nxt.begin());
			l.pop_back();
			swap(all, nxt);
		}
		for (ll j : v[i]) {
			int ind=lower_bound(all.begin(), all.end(), k-j)-all.begin();
			ans+=all.size()-ind;
		}
	}
	cout << ans;
	return 0;
}

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