oj.uz

Submission #404140

# Submission time Handle Problem Language Result Execution time Memory
404140 2021-05-13T21:54:29 Z penguinhacker San (COCI17_san) C++14
120 / 120
 58 ms 16792 KB 
#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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2160 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2788 KB Output is correct
2 Correct 4 ms 1224 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16792 KB Output is correct
2 Correct 10 ms 3572 KB Output is correct