Submission #418989

#	Time	Username	Problem	Language	Result	Execution time	Memory
418989		Blagojce	Packing Biscuits (IOI20_biscuits)	C++17	21 / 100	1093 ms	29972 KiB

biscuits

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
#include <string>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
const int mxn = 2e5+5;
mt19937 _rand(time(NULL));
clock_t z;

#include "biscuits.h"

vector<ll> A;

int m;

vector<int> v;



map<ll, ll> dp[61];

ll X;
ll gen(int pos, ll carry){
	
	if(pos == m-1){
		return (A[pos] + carry)/X + 1;
	}
	
	if(dp[pos][carry] != 0) return dp[pos][carry]-1;
	
	ll tot = A[pos] + carry;

	if(tot < X){
		return gen(pos+1, tot/2);
	}	
	ll ret = 0;
	
	//if we put : 
	ret = gen(pos+1, (tot-X) / 2);
	
	//if we don't : 
	ret += gen(pos+1, tot/2);
	
	dp[pos][carry] = ret+1;
	return ret;
}


long long count_tastiness(long long x, std::vector<long long> a) {
	
	X = x;
	
	fr(i, 0, 61) dp[i].clear();
	
	m = (int)a.size();
		
	fr(i, 0, (int)a.size()-1){
		while(a[i] >= x+2){
			a[i] -= 2;
			a[i+1] ++;
		}
		if(a[i] >= x + 2){
			ll take = (a[i] - (x + 2) + 1) / 2;
			
			ll rem = a[i] - take*2;
			//if(rem == 0) rem += x+1;
			ll mov = (a[i]-rem);
			a[i+1] += mov/2;
			a[i] -= mov;
		}
	}
	

	
	A = a;
	
	/*for(auto u : A) cout<<u<<' ';
	cout<<endl;*/
	return gen(0, 0);
}/*
int main(){
	//cout<<count_tastiness(2, {5, 0})<<endl;
	cout<<count_tastiness(1, {10, 9, 8, 7, 6})<<endl;


}
*/

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