제출 #430116

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

biscuits

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

#define F first
#define S second
#define pb push_back

using namespace std;

typedef long long ll;
const int N = 63;

ll dp[N];
ll Get(ll idx, ll i){
	if(idx == 0)
		return i;

	assert(i < dp[idx]);
	if(i < dp[idx - 1])
		return Get(idx - 1, i);
	return Get(idx - 1, i - dp[idx - 1]) + (1ll << idx);
}

int k;
ll x;
vector<ll> nw;

bool Valid(ll y){
	vector<ll> tmp = nw;
	tmp.resize(N, 0);
	for(int i = 0; i < N; i++){
		if(y >> i & 1){
			if(tmp[i] < x) return false;
			tmp[i] -= x;
		}
		if(i + 1 != N)
			tmp[i + 1] += tmp[i] / 2;
	}
	return true;
}

ll count_tastiness(ll _x, vector<ll> a) {
	a.resize(N, 0);
	k = a.size();
	nw = a;
	x = _x;
	// a.insert(a.begin(), 0);
	dp[0] = (a[0] >= x ? 2 : 1);
	for(int i = 1; i < N; i++){
		ll L = -1, R = dp[i - 1], mid;
		while(L + 1 < R){
			mid = (L + R) >> 1;
			if(Valid((1ll << i) + Get(i - 1, mid))){
				// cerr << "^ " << (1ll << i) + Get(i - 1, mid) << '\n';
				L = mid;
			} else {
				R = mid;
			}
		}
		// cerr << "!! " << Get(i - 1, 0) << ' ' << dp[i - 1] << ' ' << R << '\n';
		dp[i] = dp[i - 1] + R;
	}
	// cerr << "&& " << Valid(2) << '\n';
	// for(int i = 0; i < 5; i++) cerr << dp[i] << ' ';
	// cerr << '\n';
	return dp[N - 1];
}

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