Submission #563890

#	Time	Username	Problem	Language	Result	Execution time	Memory
563890		topovik	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	13 ms	1332 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"

#include <cassert>
#include <cstdio>
#define pb push_back

using namespace std;

typedef long long ll;
//
//#ifdef _WIN32
//# define I64 "%I64d"
//#else
//# define I64 "%lld"
//#endif
//
//long long count_tastiness(long long, std::vector<long long>);
//
//int main () {
//	int q;
//	assert(scanf("%d", &q) == 1);
//	vector<int> k(q);
//	vector<long long> x(q);
//	vector<vector<long long>> a(q);
//	vector<long long> results(q);
//	for (int t = 0;  t < q;  t++) {
//		assert(scanf("%d" I64, &k[t], &x[t]) == 2);
//		a[t] = vector<long long>(k[t]);
//		for (int i = 0;  i < k[t];  i++)
//			assert(scanf(I64, &a[t][i]) == 1);
//	}
//	fclose(stdin);
//
//	for (int t = 0;  t < q;  t++)
//		results[t] = count_tastiness(x[t], a[t]);
//	for (int t = 0;  t < q;  t++)
//		printf(I64 "\n", results[t]);
//	fclose(stdout);
//	return 0;
//}

const int M = 61;

long long count_tastiness(long long x, std::vector<long long> a) {
    while (a.size() < M) a.pb(0);
    vector <ll> b = a;
    for (int i = 1; i < M; i++) b[i] += b[i - 1] / 2ll;
    ll dp[M + 1];
    dp[0] = 1;
    for (int i = 0; i < M; i++)
    {
        if (b[i] < x) {
			dp[i + 1] = dp[i];
			continue;
		}
        dp[i + 1] = dp[i];
        ll need = max(0ll, (x - a[i]) * 2ll);
        for (int j = i - 1; j >= 0; j--)
        {
            if (b[j] >= x + need)
            {
                dp[i + 1] += dp[j];
                need = max((x + need - a[j]) * 2ll, 0ll);
            }
            else need = max((need - a[j]) * 2ll, 0ll);
        }
        if (need == 0) dp[i + 1]++;
    }
    return dp[M];
}

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