Submission #615669

#	Time	Username	Problem	Language	Result	Execution time	Memory
615669		Koosha_mv	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	61 ms	936 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&d)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define big __int128

const int N=122;
const big d=1;

ll dp[N][N];
big res[N];
int n;

int comp(int i,int j){
	big mask=(d<<(i+1))-1;
	return (res[i]&mask)<=(res[j]&mask);
}

ll count_tastiness(ll x,vector<ll> a) {
	f(i,0,N) f(j,0,N) dp[i][j]=0;
	n=a.size();
	// warning !!!!
	f(i,0,60) a.pb(0),n++;
	res[n]=(d<<(n+1))-1;
	big sum=0;
	f(i,0,n){
		sum+=d*(d<<i)*a[i];
		res[i]=min((d<<(i+1))-1,sum/x);
		//eror(res[i]);
	}
	dp[n][n]=1;
	f_(i,n,0){
		f(j,i,n+1){
			//cout<<i<<" "<<j<<" -> "<<dp[i][j]<<endl;
			if(i==0) continue ;
			int now=j;
			if(comp(i-1,now)) now=i-1;
			if(bit(res[now],i-1)==0){
				dp[i-1][now]+=dp[i][j];
			}
			else{
				dp[i-1][n]+=dp[i][j];
				dp[i-1][now]+=dp[i][j];
			}
		}
	}
	ll ans=0;
	f(i,0,n+1) ans+=dp[0][i];
	return ans;
}

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