Submission #1067841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067841		GusterGoose27	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	16 ms	1476 KiB

biscuits

#include "biscuits.h"

#include <bits/stdc++.h>

#define sz(s) ((int)(s.size()))

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
int n;

const int MAXN = 100;
ll dp[MAXN][MAXN]; // really should be 60 but im lazy

bool get(ll a, int b) {
	return (a>>b)&1;
}

ll getdp(int a, int b) {
	return a < 0 ? 1 : dp[a][b];
}

void print(vector<ll> &a) {
	for (ll v: a) cerr << v << ' ';
	cerr << '\n';
}

ll count_tastiness(ll x, vector<ll> a) {
	n = sz(a);
	vector<ll> p({0});
	// print(a);
	for (int i = 0; i < n; i++) {
		p.push_back((a[i]<<i) + p.back());
	}
	for (int i = 0; i < n; i++) {
		p[i] = p[i+1]/x;
	}
	// print(p);
	p.pop_back();
	for (int i = n; p.back() >= (1ll << i); i++) p.push_back(p.back());
	n = sz(p);
	for (int i = 0; i < n; i++) {
		p[i] = min(p[i], (1ll<<(i+1))-1);
	}
	// print(p);
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			ll res = p[j]%(1ll<<(i+1));
			if (get(res, i) && get(p[i], i)) {
				dp[i][j] = getdp(i-1, res < p[i] ? j : i) + getdp(i-1, i-1);
			}
			else {
				dp[i][j] = getdp(i-1, res < p[i] ? j : i);
			}
		}
	}
	return dp[n-1][n-1];
}

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