제출 #1284050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284050		farica	비스킷 담기 (IOI20_biscuits)	C++20	100 / 100	10 ms	960 KiB

biscuits

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

using namespace std;
using ll = long long;

long long count_tastiness(long long x, std::vector<long long> a) {
	while((int)a.size() < 63) a.push_back(0);
	vector<ll>v(63, 0), rng(63, 0);
	ll cnt = 0;
	v[0] = 1;
	for(int i=1; i<63; ++i) {
		cnt += a[i-1] * (1LL<<(i-1));
		ll ma = cnt / x;
		rng[i] = ma;
		for(int j=i-1; j>=0; --j) {
			if(!j) {
				if(ma) v[i] += 2;
				else ++v[i];
				break;
			} 
			if(ma >= (1LL<<(j+1))) {
				v[i] += 2 * v[j];
				break;
			} 
			if(ma >= (1LL<<j)) {
				v[i] += v[j];
				ma = min(ma - (1LL<<j), rng[j]);
			} else ma = min(ma, rng[j]);
		}
	}
	return v[62];
}

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