제출 #1234102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234102		madamadam3	비스킷 담기 (IOI20_biscuits)	C++20	0 / 100	1095 ms	556 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
	#define dbg(x) (cout << (x))
#else
	#define dbg(x)
#endif

typedef long long ll;
using vi =vector<int>;
using vl = vector<ll>;
#define pb push_back
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define trace(x) for (auto &el : x) {dbg(el); dbg(" ");}

ll count_tastiness(ll x, vl a) {
	int k = a.size();
	const int MAX_SUM = 100'001;
	const int BITS = 20;
	a.resize(max(k, BITS));
	trace(a); dbg("\n");

	// dbg("x: "); dbg(x); dbg(" k: "); dbg(k); dbg("\n");

	ll ans = 0;
	for (int sum = 0; sum < MAX_SUM; sum++) {
		vi tmpa(a.begin(), a.end());
		vi needed(BITS); for (int i = 0; i < BITS; i++) if (sum & (1 << i)) needed[i] += x;
		// trace(needed); dbg("\n");
		bool can = true;

		for (int bit = BITS-1; bit >= 0; bit--) {
			if (needed[bit] == 0) continue;
			int avail = tmpa[bit];
			if (avail >= needed[bit]) {
				tmpa[bit] -= needed[bit];
				needed[bit] = 0;
			} else {
				needed[bit] -= avail;
				for (int j = bit - 1; j >= 0; j--) {
					if (needed[bit] == 0) break;
					int diff = 1 << (bit - j);
					int from_here = needed[bit] * diff;
					if (from_here <= tmpa[j]) {
						needed[bit] = 0;
						tmpa[j] -= from_here;
					} else {
						int reduce = tmpa[j] / diff;
						needed[bit] -= reduce;
						tmpa[j] -= reduce * diff;
					}
				}
			}
		}

		for (int i = 0; i < BITS; i++) {
			can = can && needed[i] <= 0;
		}
		if (can) {
			ans++;
			dbg("sum is "); dbg(sum); dbg("\n");
		}
	}
	return ans;
}

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