Submission #418956

#	Time	Username	Problem	Language	Result	Execution time	Memory
418956		Blagojce	Packing Biscuits (IOI20_biscuits)	C++17	12 / 100	1 ms	332 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;

ll dp[61][2];


ll gen(int pos, bool carry){
	
	if(pos == m-1){
		return A[pos] + carry + 1;
	}
	
	if(dp[pos][carry] != -1) return dp[pos][carry];
	
	ll tot = A[pos];
	if(carry){
		tot += 1;
	}
	if(tot == 0){
		return gen(pos+1, false);
	}
	
	ll ret = 0;
	if(tot == 1){
		ret = 2*gen(pos+1, false);
	}
	else if(tot == 2){
		ret = gen(pos+1, false) + gen(pos+1, true);
	}
	else{
		ret = 2*gen(pos+1, true);
	}
	dp[pos][carry] = ret;
	return ret;
}


long long count_tastiness(long long x, std::vector<long long> a) {
	
	memset(dp, -1, sizeof(dp));
	
	m = (int)a.size();
		
	fr(i, 0, (int)a.size()-1){
		if(a[i] >= 3){
			ll rem = a[i]%2;
			if(rem == 0) rem += 2;
			ll mov = (a[i]-rem);
			a[i+1] += mov/2;
			a[i] -= mov;
		}
	}
	A = a;
	return gen(0, 0);
}/*
int main(){
	cout<<count_tastiness(1, {10, 9, 8, 7, 6})<<endl;


}*/

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