Submission #617873

#	Time	Username	Problem	Language	Result	Execution time	Memory
617873		someone	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	14 ms	1236 KiB

biscuits

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

const int N = 62;

ll nbOp = 0, nb[N], dp[N], constr[N];

ll get(ll i, ll val) {
    nbOp++;
    if(val < 0)
        return 0;
    if(i == 0)
        return min(constr[0], val) + 1;
    if(val >= constr[i]) {
        if(dp[i] == -1)
            dp[i] = get(i-1, val) + get(i-1, val - (1ll << i));
        return dp[i];
    }
    return get(i-1, val) + get(i-1, val - (1ll << i));
}

ll count_tastiness(ll x, vector<ll> a) {
    nbOp = 0;
    for(int i = 0; i < N; i++)
        nb[i] = 0;
    for(int i = 0; i < (int)a.size(); i++)
        nb[i] = a[i];
    constr[0] = nb[0];
    for(int i = 1; i < N; i++)
        constr[i] = constr[i-1] + (1ll << i) * nb[i];
    for(int i = 0; i < N; i++)
        constr[i] = min((1ll << (i+1)) - 1, constr[i] / x);

    for(int i = 0; i < N; i++)
        dp[i] = -1;

    for(int i = 0; i < N; i++)
        get(i, constr[i]);
    return dp[N-1];
}

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