Submission #303795

#	Time	Username	Problem	Language	Result	Execution time	Memory
303795		alex_velea	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	3 ms	416 KiB

biscuits

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

typedef long long int64;
typedef __int128_t int128;

#define DEBUG if(0)

long long count_tastiness(int64 x, std::vector<int64> a) {
    a.resize(kMaxK, 0);
    int128 target_carry = 0;
    int128 p = 1;
    for (int i = 0; i < (int)a.size(); i += 1) {
        target_carry += a[i] * p;
        p *= 2;
    }

    map<int128, int64> old = { {0, 1} };

    int64 ans = 1;

    int128 global_carry = 0;
    p = 1;
    for (int i = 0; i < kMaxK; i += 1) {
        global_carry += a[i] * p;

        vector<pair<int128, int64>> new_additions;
        for (auto itr = old.rbegin(); itr != old.rend(); itr++) {
            int128 carry = itr->first;
            int64 num = itr->second;

            if (global_carry + carry >= x * p) {
                DEBUG cerr << "Add + for " << i << '\n';
                ans += num;
                new_additions.emplace_back(carry - x * p, num);
            }
        }

        for (auto& itr : new_additions) {
            old[itr.first] += itr.second;
        }

        p *= 2;
        if (target_carry == global_carry) {
            break;
        }
    }

	return ans;
}

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