Submission #303779

#	Time	Username	Problem	Language	Result	Execution time	Memory
303779		alex_velea	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1051 ms	16356 KiB

biscuits

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int kMaxK = 127;

typedef long long int64;

#define DEBUG if(0)

long long count_tastiness(int64 x, std::vector<int64> a) {
    a.resize(kMaxK, 0);
    for (int i = 0; i + 1 < kMaxK; i += 1) {
        if (a[i] > x) {
            int64 carry = (a[i] - x) / 2;
            a[i + 1] += carry;
            a[i] -= carry * 2;
        }
    }

    DEBUG {
        for (int i = 0; i < 10; i += 1) {
            cerr << a[i] << '\t';
        }
        cerr << '\n';
    }

    unordered_map<int64, int64> old = { {0, 1} };

    int64 ans = 1;

    for (int i = 0; i < kMaxK; i += 1) {
        unordered_map<int64, int64> new_dp;
        for (auto& itr : old) {
            int64 carry = itr.first;
            int64 num = itr.second;

            if (carry + a[i] >= x) {
                DEBUG cerr << "Add + for " << i << '\n';
                ans += num;
                new_dp[(carry + a[i] - x) / 2] += num;
            }

            new_dp[(carry + a[i]) / 2] += num;
        }
        old = new_dp;
    }

	return ans;
}

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