| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 381510 |
2021-03-25T08:46:27 Z |
AdiZer0 |
San (COCI17_san) |
C++17 |
|
413 ms |
63656 KB |
#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)1e6 + 7;
const int INF = (int)1e9 + 7;
const ll linf = (ll)1e18 + 1;
int h[43], g[43];
ll t[N * 4];
vector<ll> mark[N];
vector<pair<int, ll>> ord;
void update(int v, int tl, int tr, int pos, int val) {
if (tl == tr) t[v] += val;
else {
int tm = tl + tr >> 1;
if (pos <= tm) update((v << 1), tl, tm, pos, val);
else update((v << 1) + 1, tm + 1, tr, pos, val);
t[v] = t[(v << 1)] + t[(v << 1) + 1];
}
}
ll get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l || l > r) return 0;
if (l <= tl && tr <= r) return t[v];
int tm = tl + tr >> 1;
return get((v << 1), tl, tm, l, r) + get((v << 1) + 1, tm + 1, tr, l, r);
}
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);
vector<ll> comp;
for (int i = 0; i < sz(ord); ++i) comp.pb(ord[i].second);
for (auto to : all) {
int last = to.first;
int l = (lower_bound(whole(pos), last) - pos.begin());
ll rem = max(0 * 1ll, k - to.second);
comp.pb(rem);
mark[l].push_back(rem);
}
sort(whole(comp));
comp.resize(unique(whole(comp)) - comp.begin());
for (int i = sz(ord) - 1; i >= 0; --i) {
ord[i].second = (lower_bound(whole(comp), ord[i].second) - comp.begin()) + 1;
update(1, 1, sz(ord) + sz(all), ord[i].second, 1);
if (!mark[i].empty()) {
for (ll to : mark[i]) {
if (to > comp[sz(comp) - 1]) continue;
int cur_pos = (lower_bound(whole(comp), to) - comp.begin()) + 1;
ways += get(1, 1, sz(ord) + sz(all), cur_pos, sz(ord) + sz(all));
}
}
}
printf ("%lld\n", ways);
return 0;
}
Compilation message
san.cpp: In function 'void update(int, int, int, int, int)':
san.cpp:24:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int tm = tl + tr >> 1;
| ~~~^~~~
san.cpp: In function 'll get(int, int, int, int, int)':
san.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int tm = tl + tr >> 1;
| ~~~^~~~
san.cpp: In function 'int main()':
san.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
40 | int n; scanf ("%d %lld", &n, &k);
| ~~~~~~^~~~~~~~~~~~~~~~~~~
san.cpp:41:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
41 | for (int i = 0; i < n; ++i) scanf ("%d %d", h + i, g + i);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23788 KB |
Output is correct |
| 2 |
Correct |
16 ms |
23788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23916 KB |
Output is correct |
| 2 |
Correct |
16 ms |
23788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
28768 KB |
Output is correct |
| 2 |
Correct |
27 ms |
24172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
33704 KB |
Output is correct |
| 2 |
Correct |
74 ms |
25060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
413 ms |
63656 KB |
Output is correct |
| 2 |
Correct |
204 ms |
31068 KB |
Output is correct |
