Submission #1031309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031309		happy_node	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	47 ms	1372 KiB

biscuits

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

map<ll, ll> dp;

vector<ll> s;

ll x;

ll g(ll n) {
	if(n<=0) return 0;
	if(n==1) return 1;
	if(dp.count(n)) return dp[n];
	ll b=0, p=1;
	while(p<n) b++,p*=2;
	p/=2;
	b--;
	return dp[n]=g(p)+g(min(n,1+s[b]/x)-p);
}
 
long long count_tastiness(long long X, std::vector<long long> a) {
	x=X;
	while(a.size()<60) a.push_back(0);
 	
 	s.clear();
 	dp.clear();
 	ll sum=0;
 	for(int i=0;i<60;i++) {
 		sum+=(1LL<<i)*a[i];
 		s.push_back(sum);
 	}

 	return g(1LL<<60);
}

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