제출 #303297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303297		jtnydv25	비스킷 담기 (IOI20_biscuits)	C++17	100 / 100	430 ms	1016 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll count_tastiness(ll x, vector<ll> a) {
	int k = 60;
	a.resize(k);
	ll val = 0;
	vector<ll> prefixes(60);
	for(int i = 0; i < k; i++){
		val += a[i] << i;
		// (prefix[i] + 2^i) * x <= val
		ll maxVal = val / x - (1LL << i) + 1;
		
		if(maxVal >= (1LL << i)) prefixes[i] = 1LL << i;
		else{
			prefixes[i] = max(0LL, maxVal);
		}
	}
	map<ll, ll> dp;
	dp[1] = 1;
	for(int i = 1; i <= k; i++){
		map<ll, ll> cp_dp = dp;
		dp.clear();
		// dp[z] = # possible with the value of smallest i bits <= z
		for(auto it : prefixes){
			ll v = it & ((1LL << i) - 1);
			if(v >> (i - 1) & 1){
				ll t = v ^ (1LL << (i - 1));
				dp[v] = cp_dp[1LL << (i-1)]; // ALL
				dp[v] += cp_dp[min(t, prefixes[i - 1])];
			}
			else dp[v] = cp_dp[v];
		}
		dp[1LL << i] = cp_dp[1LL << (i - 1)] + cp_dp[prefixes[i - 1]];
	}
	return dp[1LL << k];
	
}

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