Submission #738505

#	Time	Username	Problem	Language	Result	Execution time	Memory
738505		bobthebuilder	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	71 ms	1328 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define lowb(x) (x&(-x))
#define ALL(_x) _x.begin(),_x.end()
#define pii pair<int,int>
#define f first
#define s second
#define SORT_UNIQUE(x) sort(ALL(x)),x.erase(unique(ALL(x)),x.end())
#define ll long long
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
const int maxn=2e5+5;
const int INF=0x3f3f3f3f;
map<ll,ll> dp;
ll tot[70];
ll x;
ll rec(ll n){
	if(n<=0) return 0;
	if(n==1) return 1; 
	if(dp.count(n)) return dp[n];
	int i=ceil(log2(n))-1;
	return dp[n]=(rec((1LL<<i))+rec(min(n,tot[i]/x+1)-(1LL<<i)));
}
long long count_tastiness(long long X, std::vector<long long> a) {
	dp.clear();
	x=X;
	while(sz(a)<60) a.pb(0);
	tot[0]=a[0];
	REP1(i,59){
		tot[i]=tot[i-1]+a[i]*(1LL<<i);
	}
	return rec(1LL<<60);;
}

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