제출 #303977

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

biscuits

// Peyman !
#include "biscuits.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;

const int N = 62;

vector<ll> a;

ll dp[N + 1], sz[N + 1], x;

bool Valid(ll A){
	ll nw = 0;
	for(int i = 0; i < 62; i++){
		nw = (nw / 2) + (a[i]);
		if(A >> i & 1){
			if(x > nw) return false;
			nw -= x;
		}
	}
	return true;
}
ll Get(int bt, ll idx){
	if(bt == 0){
		return idx;
	}
	if(idx < dp[bt - 1])
		return Get(bt - 1, idx);
	return Get(bt - 1, idx - dp[bt - 1]) + (1ll << bt);
}

ll count_tastiness(ll _x, vector<ll> _a) {
	a = _a;
	x = _x;
	a.resize(N, 0);

	dp[0] = (a[0] >= x ? 2 : 1);

	for(int i = 1; i < N; i++){
		ll L = 0, R = dp[i - 1] + 1, mid;
		while(L + 1 < R){
			mid = (L + R) >> 1;
			if(Valid(Get(i - 1, mid - 1) + (1ll << i))) L = mid; 
			else R = mid;
		}
		sz[i] = L;
		dp[i] = dp[i - 1] + L;
	}
	return dp[N - 1];}

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