Submission #1110539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110539		omar1312	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	308 ms	25008 KiB

bobek

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const int mod = 1000000007;
const int N = 200005;
ll a[N+2], dp[N+2];
void solve(){
	ll n, k;
	cin>>n>>k;
	for(int i = 0; i < n; i++){
		cin>>a[i];
	}
	ll dumb = n / 2, dumb2 = n - dumb;
	vector<ll> v1, v2;
	for(int i = 0; i < (1 << dumb); i++){
		ll cost = 0;
		for(int j = 0; j < dumb; j++){
			if((i >> j) & 1){
				cost += a[j];
			}
		}
		v1.pb(cost);
	}
	for(int i = 0; i < (1 << dumb2); i++){
		ll cost = 0;
		for(int j = 0; j < dumb2; j++){
			if((i >> j) & 1){
				cost += a[j + dumb];
			}
		}
		v2.pb(cost);
	}
	sort(all(v1));
	sort(all(v2));
	ll ans = 0;
	for(auto i : v1){
		if(i > k)break;
		auto it = upper_bound(all(v2), k - i);
		--it;
		ans += it - v2.begin() + 1;
	}
	cout<<ans;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	//cin>>tt;
	while(tt--){
		solve();
		cout<<'\n';
	}
}

• 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