oj.uz

Submission #48958

# Submission time Handle Problem Language Result Execution time Memory
48958 2018-05-20T14:35:46 Z doowey Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 497 ms 21208 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 2 ms 672 KB Output is correct
7 Correct 2 ms 672 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct
2 Correct 2 ms 672 KB Output is correct
3 Correct 3 ms 672 KB Output is correct
4 Correct 2 ms 672 KB Output is correct
5 Correct 2 ms 672 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 680 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 680 KB Output is correct
2 Correct 2 ms 704 KB Output is correct
3 Correct 2 ms 704 KB Output is correct
4 Correct 2 ms 704 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 704 KB Output is correct
7 Correct 2 ms 704 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2296 KB Output is correct
2 Correct 102 ms 5740 KB Output is correct
3 Correct 497 ms 21080 KB Output is correct
4 Correct 101 ms 21080 KB Output is correct
5 Correct 20 ms 21080 KB Output is correct
6 Correct 12 ms 21080 KB Output is correct
7 Correct 12 ms 21080 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 21080 KB Output is correct
2 Correct 34 ms 21080 KB Output is correct
3 Correct 169 ms 21080 KB Output is correct
4 Correct 2 ms 21080 KB Output is correct
5 Correct 9 ms 21080 KB Output is correct
6 Correct 25 ms 21080 KB Output is correct
7 Correct 12 ms 21080 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 21080 KB Output is correct
2 Correct 152 ms 21080 KB Output is correct
3 Correct 151 ms 21080 KB Output is correct
4 Correct 2 ms 21080 KB Output is correct
5 Correct 107 ms 21080 KB Output is correct
6 Correct 370 ms 21208 KB Output is correct
7 Correct 64 ms 21208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 21208 KB Output is correct
2 Correct 36 ms 21208 KB Output is correct
3 Correct 14 ms 21208 KB Output is correct
4 Correct 2 ms 21208 KB Output is correct
5 Correct 12 ms 21208 KB Output is correct
6 Correct 314 ms 21208 KB Output is correct
7 Correct 12 ms 21208 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 21208 KB Output is correct
2 Correct 100 ms 21208 KB Output is correct
3 Correct 13 ms 21208 KB Output is correct
4 Correct 13 ms 21208 KB Output is correct
5 Correct 126 ms 21208 KB Output is correct
6 Correct 42 ms 21208 KB Output is correct
7 Correct 167 ms 21208 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 21208 KB Output is correct
2 Correct 38 ms 21208 KB Output is correct
3 Correct 14 ms 21208 KB Output is correct
4 Correct 428 ms 21208 KB Output is correct
5 Correct 139 ms 21208 KB Output is correct
6 Correct 27 ms 21208 KB Output is correct
7 Correct 20 ms 21208 KB Output is correct