Submission #899499

#	Time	Username	Problem	Language	Result	Execution time	Memory
899499		MongHwa	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	214 ms	22732 KiB

bobek

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define ll long long

ll val;
vector<ll> v1, v2;
vector<ll> target1, target2;

void go(int k, vector<ll>& v, vector<ll>& t, int d)
{
	if(k == d)
	{
		if(val > 0)
			t.push_back(val);
		return;
	}

	val += v[k];
	go(k+1, v, t, d);
	val -= v[k];
	go(k+1, v, t, d);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; ll m;
	cin >> n >> m;

	for(int i = 0; i < n; i++)
	{
		ll x;
		cin >> x;

		if(i < n/2)
			v1.push_back(x);
		else
			v2.push_back(x);
	}

	int d1 = v1.size(), d2 = v2.size();
	go(0, v1, target1, d1);
	go(0, v2, target2, d2);

	sort(target1.begin(), target1.end());
	sort(target2.begin(), target2.end());

	ll ans = 0;
	ans += (upper_bound(target1.begin(), target1.end(), m) - target1.begin());
	ans += (upper_bound(target2.begin(), target2.end(), m) - target2.begin());

	for(int i = 0; i < (int)target1.size(); i++)
		ans += (upper_bound(target2.begin(), target2.end(), m-target1[i]) - target2.begin());
	ans++;

	cout << ans << '\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