# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
250520 | Vladikus004 | San (COCI17_san) | C++14 | 351 ms | 8896 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define inf 2e9
#define int long long
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
const int N = 41;
int n, h[N], g[N];
ll k;
vector <ll> v1[21], v2[21];
bool can(int mask){
int mx = -inf;
for (int i = 0; i < n; i++){
if (!(mask & (1LL<<i))) continue;
if (mx > h[i]) return false;
mx = h[i];
}
return true;
}
ll get_sum(int mask){
ll sum = 0;
for (int i = 0; i < n; i++){
if (!(mask & (1LL<<i))) continue;
sum += g[i];
}
return sum;
}
int f(int x, int sz){
int cnt = 0;
for (int i = sz - 1; i >= 0; i--){
if ((1LL<<i)&x) return cnt;
cnt++;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
// cout << __builtin_ctz(4) << "\n";
cin >> n >> k;
for (int i = 0; i < n; i++){
cin >> h[i] >> g[i];
}
if (n & 1){
h[n] = inf;
++n;
}
int ans = 0;
int sz = n / 2;
for (int mask = 1; mask < (1LL<<sz); mask++){
if (can(mask)){
ll sum = get_sum(mask);
v1[f(mask, sz)].push_back(sum);
if (sum >= k)
ans += 1;
}
}
for (int mask = 1; mask < (1LL<<sz); mask++){
int cmask = mask<<sz;
if (can(cmask)){
ll sum = get_sum(cmask);
v2[__builtin_ctz(cmask) - sz].push_back(sum);
if (sum >= k)
ans += 1;
}
}
for (int i = 0; i < sz; i++){
for (int g = 0; g < sz; g++){
if (h[sz - 1 - i] > h[g + sz]) continue;
for (int j = 0; j < v1[i].size(); j++){
// cout << i << " : " << v1[i][j] << "\n";
ans += v2[g].size()-(lower_bound(all(v2[g]), k - v1[i][j])-v2[g].begin());
}
}
}
cout << ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |