Submission #1290062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290062		mariaclara	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	11 ms	944 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define sz(x) (int)x.size()
#define pb push_back

ll x, s[61], dp[61];

ll solve(ll n, int b) { 
    if(n == 1) return 1;
    if(n < 1) return 0;
    // 2^b < n <= 2^(b+1)
    while((1LL<<b) >= n) b--;
    return dp[b] + solve(min(n, s[b]/x + 1) - (1LL<<b), b);
}

ll count_tastiness(ll X, vector<ll> a) {
    x = X;
    s[0] = a[0];
    dp[0] = 1;

    for(ll i = 1, pot = 2; i <= 60; i++, pot *= 2) {
        s[i] = s[i-1];
        if(i < sz(a)) s[i] += pot * a[i];
    }

    for(int i = 1; i <= 60; i++)
        dp[i] = solve(1LL<<i, i-1);

    return dp[60];
}

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