Submission #47618

#	Time	Username	Problem	Language	Result	Execution time	Memory
47618		IvanC	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	251 ms	21660 KiB

bobek

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> S1,S2,V1,V2;
ll N,M,ptr,A,B,tot;

void brute1(ll val,int pos){
	if(pos == A){
		S1.push_back(val);
		return;
	}
	brute1(val + V1[pos],pos+1);
	brute1(val,pos+1);
}

void brute2(ll val,int pos){
	if(pos == B){
		S2.push_back(val);
		return;
	}
	brute2(val + V2[pos],pos+1);
	brute2(val,pos+1);
}

int main(){
	cin >> N >> M;
	for(int i = 0;i<N;i++){
		ll x;
		cin >> x;
		if(i & 1) V1.push_back(x);
		else V2.push_back(x);
	}
	A = V1.size();
	brute1(0,0);
	sort(S1.begin(),S1.end());
	//for(ll i : S1) cout << " " << i;
	//cout << endl;
	B = V2.size();
	brute2(0,0);
	sort(S2.rbegin(),S2.rend());
	//for(ll i : S2) cout << " " << i;
	//cout << endl;
	for(int i = 0;i<S1.size();i++){
		//printf("S1[%d] %lld S2[%lld] %lld\n",i,S1[i],ptr,S2[ptr]);
		if(S1[i] > M) break;
		while(S1[i] + S2[ptr] > M){
			ptr++;
			//printf("S1[%d] %lld S2[%lld] %lld\n",i,S1[i],ptr,S2[ptr]);
		}
		tot += S2.size() - ptr;
	}
	cout << tot << endl;
	return 0;
}

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<S1.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: 10 / 10