제출 #408615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408615		priority_queue	비스킷 담기 (IOI20_biscuits)	C++14	0 / 100	1085 ms	348 KiB

biscuits

#include <bits/stdc++.h>

#define forint(i, N) for (long long i = 0; i < (N); i++)

using namespace std;

void takeout(vector<long long>& a, long long pos, long long val) {
	
	if (a[pos] * (1ll << pos) < val) {
		takeout(a, pos-1, val - a[pos] * (1ll << pos));
		a[pos] = 0;
		return;
	}

	long long v = val / (1ll << pos);

	a[pos] -= v;

	if (v * (1ll << pos) < val) {
		takeout(a, pos-1, val - v * (1ll << pos));	
	}
}


long long count(long long x, vector<long long>& a, long long max_y) {

	if (max_y == 0) {
		return 1;
	}

	if (max_y == 1) {
		if (a[0] >= x) {
			return 2; // 0 & 1;
		}
		else {
			return 1; // 0 only 
		}
	}

	long long k = a.size();
	vector<long long> sum(61, 0);

	sum[0] = a[0];
	for (long long i = 1; i < k; i++) {
		sum[i] = sum[i - 1] + a[i] * (1ll << i);
	}

	for (long long i = k; i < 61; i++) {
		sum[i] = sum[i-1];
	}

	// find i
	long long i = 0;
	while ((1ll << i) < max_y) {
		i++;
	}

	if (max_y == (1ll << i)) {
		if (sum[i] >= max_y * x) { 
			return count(x, a, max_y - 1) + 1;
		}
		else {
			return count(x, a, max_y - 1);
		}
	}

	long long aa = count(x, a, 1ll << (i-1));

	if (sum[i-1] < (1ll << (i-1)) *x ) {
		return aa;
	}
	else {
		vector<long long> b(i, 0);
		forint(j, i) {
			b[j] = a[j];
		}

		takeout(b, i-1, (1ll << (i-1))*x);

		return  aa + count(x, b, max_y - (1ll << (i-1))) - 1; // 0 has been counted
	}
 }


long long count_tastiness(long long x, vector<long long> a) {
	return count(x, a, 1e18);
}

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