# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
681720 | Doncho_Bonboncho | Ice Hockey World Championship (CEOI15_bobek) | C++14 | 352 ms | 20764 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>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;
ll a[MAX_N];
std::vector<ll> l, r;
int main () {
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
ll n, m;
std::cin>>n>>m;
for( int i=0 ; i<n ; i++ ) std::cin>>a[i];
int mid = n/2;
for( int mask = 0; mask < ( 1 << mid ) ; mask++ ){
ll currSum = 0;
for( int j=0 ; j<mid ; j++ )
if( (1<<j)&mask ) currSum += a[j];
l.push_back( currSum );
// std::cerr<<"l "<<currSum<<"\n";
}
for( int mask = 0; mask < ( 1 << ( n-mid) ) ; mask++ ){
ll currSum = 0;
for( int j=0 ; j<n-mid ; j++ )
if( (1<<j)&mask ) currSum += a[j];
r.push_back( currSum );
// std::cerr<<"r "<<currSum<<"\n";
}
std::sort( l.begin(), l.end() );
std::sort( r.begin(), r.end() );
ll nas = 0;
for( int i=0 ; i<l.size() ; i++ ){
ll cur = m-l[i];
ll ind = std::upper_bound( r.begin(), r.end(), cur ) - r.begin();
nas += ind;
}
std::cout<<nas<<"\n";
/*
for( int i=0 ; i<n ; i++ ){
ll curr = a[i];
int sz = v.size();
for( int j=0 ; j<sz ; j++ ){
ll currS = v[j] + curr;
// std::cerr<<v[j]<<" + "<<curr<<" = "<<currS<<" ? "<<m<<"\n";
if( currS <= m ){
// std::cerr<<" mina\n ";
v.push_back( currS );
}
}
//if( curr < m ) v.push_back( curr );
}
std::cout<<v.size()<<"\n";
*/
return 0;
}
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... |