Submission #306365

#	Time	Username	Problem	Language	Result	Execution time	Memory
306365		lohacho	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	16 ms	896 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const LL INF = (LL)1e9 + 7;
const LL NS = (LL)1e5 + 4;
LL dp[64], mxget[64];

LL count_tastiness(LL x, vector<LL> a) {
    while((int)a.size() < 60) a.push_back(0);
    memset(dp, 0, sizeof(dp));
    memset(mxget, 0, sizeof(mxget));
    for(LL i = 0; i < (LL)a.size(); ++i){
        mxget[i] = a[i];
        if(i) mxget[i] += mxget[i - 1] / 2;
    }
    for(LL i = 0; i < (LL)a.size(); ++i){
        if(mxget[i] >= x){
            LL need = max(0ll, x - a[i]) * 2;
            for(LL last = i - 1; last >= 0; --last){
                if(mxget[last] >= x + need){
                    if(last) dp[i] += dp[last - 1];
                    else dp[i] += 1;
                    need = max(0ll, need + x - a[last]) * 2;
                }
                else{
                    need = max(0ll, need - a[last]) * 2;
                }
            }
            if(!need) ++dp[i];
        }
        if(i) dp[i] += dp[i - 1];
        else dp[i] += 1;
    }
    return dp[(LL)a.size() - 1];
}

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