# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
482638 | robell | Ice Hockey World Championship (CEOI15_bobek) | C++14 | 1101 ms | 152044 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>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
#define int long long
#define pb push_back
#define eb emplace_back
#define countbits __builtin_popcount
#define beg0 __builtin_clz
#define terminal0 __builtin_ctz
#define f first
#define s second
int mod=1e9+7;
void setIO(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
void setIO(string f){
freopen((f+".in").c_str(),"r",stdin);
freopen((f+".out").c_str(),"w",stdout);
setIO();
}
ll N, M, c[40];
ll s1[(1<<20)], s2[(1<<20)];
vector<int> v1, v2;
map<ll,int> m;
set<ll> store;
vector<ll> vals;
vector<ll> counts={0};
void setup1(){
for (int i=1;i<(1<<v1.size());i++){
for (int j=0;j<v1.size();j++){
if (i&(1<<j)){
int n = i&(~(1<<j));
s1[i]=s1[n]+v1[j];
break;
}
}
}
}
void setup2(){
for (int i=1;i<(1<<v2.size());i++){
for (int j=0;j<v2.size();j++){
if (i&(1<<j)){
int n = i&(~(1<<j));
s2[i]=s2[n]+v2[j];
break;
}
}
}
}
int32_t main(){
setIO(); cin >> N >> M; s1[0]=0;s2[0]=0;
for (int i=0;i<N;i++){cin >> c[i];}
for (int i=0;i<N/2;i++) v1.pb(c[i]);
for (int i=N/2;i<N;i++) v2.pb(c[i]);
setup1();setup2();
for (int i=0;i<(1<<v1.size());i++){
m[s1[i]]++;
store.insert(s1[i]);
}
for (ll j:store) vals.pb(j);
for (ll j:store) counts.pb(counts.back()+m[j]);
ll res = 0;
for (int i=0;i<(1<<v2.size());i++){
ll diff = M-s2[i];
int l=0,r=vals.size()-1;
while (l!=r){
int mid = (l+r+1)/2;
if (vals[mid]<=diff) l=mid;
else r=mid-1;
}
if (vals[r]<=diff){
res+=counts[r+1];
}else{
res+=counts[r];
}
}
cout << res << "\n";
}
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... |
# | 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... |