제출 #830448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830448		amunduzbaev	비스킷 담기 (IOI20_biscuits)	C++17	21 / 100	8 ms	980 KiB

biscuits

#include "biscuits.h"

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

#define ar array
typedef long long ll;
//~ #defien int ll

ll count_tastiness(ll x, vector<ll> a) {
	
	int k = 60;
	a.resize(k);
	vector<ll> pref(k);
	for(int i=0;i<k;i++){
		if(i) pref[i] = pref[i - 1];
		pref[i] += a[i] * (1ll << i);
	}
	for(int i=0;i<k;i++){
		pref[i] /= x;
	}
	
	//~ for(int i=0;i<k;i++){
		//~ cout<<pref[i]<<" ";
	//~ }
	//~ cout<<"\n";
	
	ll sum = 1;
	vector<ll> dp(k), L(k), toob(k);
	
	for(int i=0;i<k;i++){
		L[i] = (1ll << (i + 1));
		if(pref[i] < (1ll << i)) continue;
		L[i] = pref[i] + 1;
		ll L_ = L[i] - (1ll << i);
		dp[i] = sum;
		
		for(int j=i-1;~j;j--){
			if(L_ <= (1ll << j)){
				toob[i] += dp[j];
			} else {
				if(L[j] <= L_) break;
				else toob[i] -= toob[j], L_ -= (1ll << j);
			}
		}
		
		dp[i] -= toob[i];
		
		//~ cout<<dp[i]<<" ";
		sum += dp[i];
	}
	//~ cout<<"\n";
	
	return sum;
}

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