Submission #394857

#	Time	Username	Problem	Language	Result	Execution time	Memory
394857		snasibov05	Packing Biscuits (IOI20_biscuits)	C++14	0 / 100	5 ms	332 KiB

biscuits

#include "biscuits.h"

#define int long long

const int kmax = 65;

using namespace std;

int binpow(int n, int p){
    if (p == 0) return 1;
    if (p % 2 == 0){
        int k = binpow(n, p/2);
        return k * k;
    }
    else{
        return binpow(n, p-1) * n;
    }
}

int count_tastiness(int x, vector<int> a) {
    vector<int> bin(kmax);

    for (int i = a.size() - 1; i >= 0; --i) {
        bin[i] = a[i];
    }

    for (int i = 0; i < kmax - 1; ++i) {
        if (bin[i] == 0) continue;
        bin[i+1] += (bin[i] - 1) / 2;
        bin[i] -= (bin[i] - 1) / 2 * 2;
    }

    int k = 0;
    for (int i = 0; i < kmax; ++i) {
        if (bin[i] > 0) k++;
    }

    vector<int> to_zero(kmax);
    int z = -1;
    for (int i = kmax - 1; i >= 0; --i) {
        if (bin[i] == 0) z = i;
        if (bin[i] == 2) to_zero[i] = z - i;
    }

    int ans = binpow(2, k);

    int cnt = 0;
    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j < kmax; ++j) {
            if (to_zero[j] == i) cnt++;
        }

        ans += max((cnt - i + 1), 0ll) * binpow(2, k - i);
    }

    return ans;

}

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