제출 #1075248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1075248		allin27x	비스킷 담기 (IOI20_biscuits)	C++17	56 / 100	27 ms	1340 KiB

biscuits

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

vector<int> S; int X;
map<int,int> memo;

int dp(int n){
	if (n<=0) return 0;
	if (memo[n]) return memo[n];
	int l2=0; int t=n-1; while (t) l2++, t/=2; l2--;
	return memo[n] = dp(1ll<<l2) + dp(min(1+ S[l2]/X, n) - (1ll<<l2));
}
long long count_tastiness(long long x, std::vector<long long> a) {
	memo.clear();
	a.resize(max((int)a.size(), 61ll), 0); int k = a.size();
	vector<int> s(k,0);
	s[0] = a[0]; X=x;
	for (int i = 1; i < k; i++) {
		s[i] = s[i - 1] + a[i] * (1ll<<i);
	}
	S=s;
	memo[1] = 1;
	return dp(1e18+2);

}

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