Submission #393377

#	Time	Username	Problem	Language	Result	Execution time	Memory
393377		fedoseevtimofey	Packing Biscuits (IOI20_biscuits)	C++14	0 / 100	2 ms	332 KiB

biscuits

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>

using namespace std;
 
typedef long long ll;

#include "biscuits.h"

long long count_tastiness(long long x, std::vector<long long> a) {
  /*int k = a.size();
  vector <pair <ll, ll>> dp;
  dp.push_back({0, 1});
  for (int i = 0; i < k; ++i) {
    vector <pair <ll, ll>> ndp;
    for (auto p : dp) {
      p.first += a[i];
      if (p.first >= x) {
        ndp.push_back(make_pair((p.first - x) / 2, p.second));
      }
      ndp.push_back(make_pair(p.first / 2, p.second));
    }
    sort(ndp.begin(), ndp.end());
    dp.clear();
    for (auto p : ndp) {
      if (dp.empty() || dp.back().first != p.first) dp.push_back(p);
      else dp.back().second += p.second;
    }
  }
  ll ans = 0;
  for (auto p : dp) ans += p.second;
  return ans;*/
  int k = a.size();
  ll ans = 0;
  for (int go = 0; go < min((ll)100000, 1LL << k); ++go) {
    ll have = 0;
    int bad = 0;
    for (int i = 0; i < k; ++i) {
      have += a[i];
      if (go & (1LL << i)) {
        have -= x;
        if (have < 0) {
          bad = 1;
          break;
        }
      }
      have /= 2;
    }
    if (!bad) ++ans;
  }
  return ans;
}

#ifdef LOCAL
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int q;
  cin >> q;
	vector<int> k(q);
	vector<long long> x(q);
	vector<vector<long long>> a(q);
	vector<long long> results(q);
	for (int t = 0; t < q; t++) {
    cin >> k[t] >> x[t];
		a[t] = vector<long long>(k[t]);
		for (int i = 0; i < k[t]; i++) {
      cin >> a[t][i];
		}
	}
	for (int t = 0; t < q; t++) {
		results[t] = count_tastiness(x[t], a[t]);
	}
	for (int t = 0; t < q; t++) {
	  cout << results[t] << '\n';;
	}
}
#endif

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23