Submission #590035

#	Time	Username	Problem	Language	Result	Execution time	Memory
590035		Blagojce	Ice Hockey World Championship (CEOI15_bobek)	C++11	100 / 100	321 ms	20892 KiB

bobek

#include <bits/stdc++.h>
#define fr(i, n, m) for(ll i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n;
ll m;

ll a[40];

int main(){
	cin >> n >> m;
	fr(i, 0, n){
		cin >> a[i];
	}
	
	int p1 = n/2;
	int p2 = n-p1;
	
	vector<ll> v1;
	fr(i, 0, (1<<p1)){
		ll sum = 0;
		fr(j, 0, p1){
			if(i&(1LL<<j)){
				sum += a[j];
			}
		}
		if(sum <= m){
			v1.pb(sum);
		}
	}
	
	vector<ll> v2;
	fr(i, 0, (1<<p2)){
		ll mask = (i<<p1);
		ll sum = 0;
		fr(j, p1, p1+p2){
			if(mask&(1LL<<j)){
				sum += a[j];
			}
		}
		if(sum <= m){
			v2.pb(sum);
		}
		
	}
	sort(all(v1));
	sort(all(v2));
	
	int pos = 1;
	ll ans = 0;
	for(int i = (int)v1.size()-1; i >= 0; i --){
		while(pos < (int)v2.size() && v2[pos] + v1[i] <= m){
			++pos;
		}
		ans += pos;
	
	}
	cout<<ans<<endl;
	
	
	
	
	
	
	
	
	
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10