Submission #743458

#	Time	Username	Problem	Language	Result	Execution time	Memory
743458		NintsiChkhaidze	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	311 ms	20840 KiB

bobek

#include <bits/stdc++.h>
#define ll long long
#define s second
#define pb push_back
#define f first
#define int ll 
using namespace std;
 
const int N = 45;
int a[N],b[N];
vector <int> v1,v2;

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,lim;
	cin>>n>>lim;
	
	for (int i =1; i<=n;i++){
		if (i > n/2) cin>>b[i - n/2];
		else cin>>a[i];
	}
	int m1 = n/2,m2 = n - m1;
	for (int i = 1; i < (1<<m1); i++){
		int cost=0;
		for (int j = 1; j <= m1; j++){
			if ((i & (1<<(j - 1)))) {
				cost += a[j];
			}
		}
		if (cost <= lim) v1.pb(cost);
	}
	
	for (int i = 1; i < (1<<m2); i++){
		int cost=0;
		for (int j = 1; j <= m2; j++){
			if ((i & (1<<(j - 1)))) {
				cost += b[j];
			}
		}
		if (cost <= lim) v2.pb(cost);
	}
	
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	
	int ans = 1 + v1.size() + v2.size(),r=-1;
	for (int i = v1.size()-1; i >= 0; i--){
		while (r + 1 < v2.size() && v1[i] + v2[r + 1] <= lim) ++r;
		ans += r + 1;
	}
	cout<<ans;
}

/*
5 1000
100 1500 500 500 1000
*/

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:49:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while (r + 1 < v2.size() && v1[i] + v2[r + 1] <= lim) ++r;
      |          ~~~~~~^~~~~~~~~~~

• 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