Submission #608990

#	Time	Username	Problem	Language	Result	Execution time	Memory
608990		Tigryonochekk	Packing Biscuits (IOI20_biscuits)	C++17	21 / 100	1086 ms	15720 KiB

biscuits

#include <iostream>
#include "biscuits.h"
#include <vector>
#include <map>
#define ll long long
#define pll pair<ll, ll>
using namespace std;

map<ll, ll> dp0, dp1;

long long count_tastiness(long long x, vector<long long> a) {
	ll ans = 0;
	for (int i = 0; a.size() < 63; i++)
		a.push_back(0);
	int k = a.size();
	dp0[a[0]] = 1;
	if (a[0] >= x) {
		dp0[a[0] - x] = 1;
	}
	for (int i = 1; i < k; i++) {
		for (pll jp : dp0) {
			ll j = jp.first, val = jp.second;
			dp1[j / 2 + a[i]] += val;
			if (j / 2 + a[i] >= x) {
				dp1[j / 2 + a[i] - x] += val;
			}
		}
		/*for (pll jp : dp1) {
			cout << i << " " << jp.first << " " << jp.second << endl;
		}*/
		dp0 = dp1;
		dp1.clear();
	}
	ans = dp0[0];
	dp0.clear();
	return ans;
}
	
/*
2
3 2 
2 1 2 
3 3
5 2 1
*/

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