Submission #568503

#	Time	Username	Problem	Language	Result	Execution time	Memory
568503		2fat2code	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	42 ms	1308 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
#define int long long
using namespace std;

const int nmax = 60;

int k, sum[nmax], total, X;

unordered_map<int, int>prec;

int calculate(int n){
  //  cout << n << '\n';
    if(prec.count(n)){
        return prec[n];
    }
    else if(n < 0LL) return 0LL;
    else{
        int largestbit = 0;
        while((1LL << (largestbit + 1LL)) <= n){
            ++largestbit;
        }
        prec[n] = calculate((1LL << largestbit) - 1LL) + calculate(min(n, sum[largestbit] / X) - (1LL << largestbit));
        return prec[n];
    }
}

int count_tastiness(int x, vector<int> a) {
    total = 0;
    X = x;
    prec.clear();
    k = (int)a.size();
    for(int i=0;i<k;i++) sum[i] = 0;
    for(int i=0;i<k;i++){
        total += (a[i] * (1LL << i));
        sum[i] += (a[i] * (1LL << i));
        if(i) sum[i] += sum[i - 1];
    }
    for(int i=k;i<60;i++) sum[i] = sum[i - 1];
    prec[0] = 1;
    int ans =  calculate(total / x);
    return ans;
}

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