Submission #48958

#	Time	Username	Problem	Language	Result	Execution time	Memory
48958		doowey	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	497 ms	21208 KiB

bobek

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define TEST freopen("in.txt","r",stdin);
#define ab(a) ((a < 0) ? (-(a)) : (a))
#define all(a) a.begin(), a.end()
 
ll cst;
 
vector<ll> costs(vector<ll> split){
  int n = (int)split.size();
  ll sum = 0;
  vector<ll>ret;
  for(int i = 0;i < (1 << n); i ++ ){
    sum = 0;
    for(int j = 0;j < n;j ++ ){
      if(i & ( 1 << j)){
        sum += split[j];
      }
    }
    if(sum <= cst)ret.push_back(sum);
  } 
  sort(all(ret));
  return ret;
}

int main(){
  fastIO;
  int n;
  cin >> n >> cst;
  ll w[n];
  for(int i = 0; i < n;i ++ ){
    cin >> w[i];
  }
  if(n == 1){
    cout << 1 + (w[0] <= cst) << "\n";
    return 0;
  }
  vector<ll> fhf,shf;
  for(int i = 0;i < n/2;i ++){
    fhf.push_back(w[i]);
  }
  for(int i = n/2;i < n;i ++ ){
    shf.push_back(w[i]);
  } 
  fhf = costs(fhf);
  shf = costs(shf);
  ll ans = 0;
  int p = fhf.size() - 1;
  for(int i = 0;i < shf.size(); i ++){
    while(p > 0 and shf[i] + fhf[p] > cst){
      p--;
    }
    ans += p + 1;
  }
  cout << ans << "\n";
  return 0;
}

Compilation message (stderr)

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