#include <bits/stdc++.h>
#define pb push_back
#define whole(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = (int)3e5 + 7;
const int INF = (int)1e9 + 7;
const ll linf = (ll)1e18 + 1;
int h[60], g[60];
vector<ll> t[N * 4];
vector<pair<int, ll>> ord;
void build(int v, int tl, int tr) {
if (tl == tr) t[v].pb(ord[tl - 1].second);
else {
int tm = tl + tr >> 1;
build((v << 1), tl, tm);
build((v << 1) + 1, tm + 1, tr);
merge(whole(t[(v << 1)]), whole(t[(v << 1) + 1]), back_inserter(t[v]));
}
}
ll get(int v, int tl, int tr, int l, int r, ll val) {
if (tl > r || tr < l || l > r) return 0;
if (l <= tl && tr <= r) {
if (lower_bound(whole(t[v]), val) == t[v].end()) return 0;
int pos = (lower_bound(whole(t[v]), val) - t[v].begin());
int res = sz(t[v]) - pos;
return res;
}
int tm = tl + tr >> 1;
return get((v << 1), tl, tm, l, r, val) + get((v << 1) + 1, tm + 1, tr, l, r, val);
}
int main() {
ll k;
int n; scanf ("%d %lld", &n, &k);
for (int i = 0; i < n; ++i) scanf ("%d %d", h + i, g + i);
int half = n / 2;
ll ways = 0;
vector<pair<int, ll>> all;
for (int i = 1; i < (1 << half); ++i) {
bool bad = false;
int p = -1;
ll gold = 0;
for (int j = 0; j < half; ++j) {
if ((i >> j) & 1) {
if (p == -1) gold += g[j], p = j;
else if (h[p] <= h[j]) gold += g[j], p = j;
else bad = true;
}
}
if (bad) continue;
if (gold >= k) ++ways;
all.pb({h[p], gold});
}
int rem = n - half;
for (int i = 1; i < (1 << rem); ++i) {
bool bad = false;
int st = -1, p = -1;
ll gold = 0;
for (int j = 0; j < rem; ++j) {
if ((i >> j) & 1) {
if (p == -1) st = j + half, p = j + half, gold += g[j + half];
else if (h[p] <= h[j + half]) p = j + half, gold += g[j + half];
else bad = true;
}
}
if (bad) continue;
if (gold >= k) ++ways;
ord.pb({h[st], gold});
}
sort(whole(ord));
vector<int> pos;
for (int i = 0; i < sz(ord); ++i) pos.pb(ord[i].first);
build(1, 1, sz(ord));
for (auto to : all) {
int last = to.first;
int l = (lower_bound(whole(pos), last) - pos.begin()) + 1;
int r = sz(ord);
ll rem = max(0 * 1ll, k - to.second);
ways += (get(1, 1, sz(ord), l, r, rem));
}
printf ("%lld\n", ways);
return 0;
}
Compilation message
san.cpp: In function 'void build(int, int, int)':
san.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int tm = tl + tr >> 1;
| ~~~^~~~
san.cpp: In function 'll get(int, int, int, int, int, ll)':
san.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int tm = tl + tr >> 1;
| ~~~^~~~
san.cpp: In function 'int main()':
san.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
44 | int n; scanf ("%d %lld", &n, &k);
| ~~~~~~^~~~~~~~~~~~~~~~~~~
san.cpp:45:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
45 | for (int i = 0; i < n; ++i) scanf ("%d %d", h + i, g + i);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
28524 KB |
Output is correct |
| 2 |
Correct |
20 ms |
28524 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
28524 KB |
Output is correct |
| 2 |
Correct |
20 ms |
28524 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
64 ms |
42080 KB |
Output is correct |
| 2 |
Correct |
32 ms |
29548 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
157 ms |
62932 KB |
Output is correct |
| 2 |
Correct |
85 ms |
30820 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
350 ms |
65536 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
