Submission #1054120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054120		vako_p	Ice Hockey World Championship (CEOI15_bobek)	C++14	90 / 100	1072 ms	132024 KiB

bobek

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 50;
ll n,m,a[mxN],_p[2000000];
ll* p = _p + 2;
map<ll,ll> ans;
set<ll> s;
vector<ll> v;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> a[i]; 
	s.insert(0);
	ans[0]++;
	for(int bit = 1; bit < (1 << (n / 2)); bit++){
		ll x = 0;
		for(int i = 0; i < (n / 2); i++) x += a[i] * (((1 << i) & bit) > 0);
		if(x <= m){
			ans[x]++;
			s.insert(x); 
		} 
//		cout << x << ' ' << ans[x] << '\n';
	} 
	for(auto it : s) v.pb(it);
	for(int i = 0; i < v.size(); i++){
		p[i] = p[i - 1] + ans[v[i]];
	}
	ll res = p[v.size() - 1];
	for(int bit = 1; bit < (1 << ((n + 1) / 2)); bit++){
		ll x = 0;
		for(int i = 0; i < (n + 1) / 2; i++) x += a[i + n / 2] * (((1 << i) & bit) > 0);
		auto it = upper_bound(v.begin(), v.end(), m - x); 
		if(it != v.begin())	res += p[it - v.begin() - 1];
	}
	cout << res;
}

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~

• 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: 0 / 10