Submission #1185815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185815		Swan	Packing Biscuits (IOI20_biscuits)	C++20	9 / 100	22 ms	840 KiB

biscuits

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <optional>
//#define int long long
#define INP freopen("subrev.in","r",stdin)
#define OUTP freopen("subrev.out","w",stdout)
using ld = long double;
using LD = ld;
 
using namespace std;

map<int, int> g;
long long x;


bool isTwoPower(long long x) {
    long long mda = log2(x);
    long long val = (1ll << mda);
    if (val > x) val/=2;
    if (val < x) val*=2;

    return val == x;
}

long long getLargestPower(long long x) {
    if (x == 1) return 0;
    long long cur = 1;

    while((1ll << cur) < x) cur++;

    return cur - 1;
}

long long getSum(vector<long long>& v, int r) {
    long long ans = 0;
    int len = v.size() - 1;

    for (int i = 0; i <= min(len, r); i++) ans+=(1ll << i) * v[i];

    return ans;
}

long long calcF(long long n, vector<long long>& v) {
    if (n == 0) return 1;
    if (n < 0) return 0;
    if (g.count(n)) return g[n];

    long long res = 0;

    if (isTwoPower(n)) {
        long long sum = 0;
        for (int i = 0; i < v.size(); i++) {
            if ((1ll << i) <= n) sum+= v[i] * (1ll << i);
        }

        if (sum / n >= x) res++;
        res+=calcF(n - 1, v);

        g[n] = res;

        return res;
    }

    long long largestPower = getLargestPower(n);
    long long sum = getSum(v, largestPower);
    res = calcF((1ll << largestPower), v);

    if (sum / (1LL << largestPower) >= x) {
        res+=calcF(min(n, sum / x) - (1ll << largestPower), v);
        res--;
    }

    g[n] = res;

    return res;
}

long long count_tastiness(long long X, vector<long long> v) {
    g.clear();
    x = X;
    
    return calcF(1LL << 61, v);
}

/*

void solve() {
   cout << count_tastiness(3, {5, 2, 1});

   cout << endl << g[3] << endl;
}


int main() {
    ios_base::sync_with_stdio(0);
    solve();
}
    */

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