Submission #1041465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041465		boyliguanhan	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	7 ms	1112 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll count_tastiness(ll x, std::vector<ll> a) {
    ll ans=0;
    a.insert(a.begin(),0);
    while(a.size()<=60)
        a.push_back(0);
    vector<ll>dp(61),mx=a;
    for(int i=1;i<=60;i++)
        mx[i]+=mx[i-1]/2;
    dp[0]=1;
    for(int i=1;i<=60;i++) {
        if(mx[i]<x)
            dp[i]=dp[i-1];
        else {
            dp[i]=dp[i-1]+1;
            ll req=max(0ll,(x-a[i])<<1);
            for(int j=i;--j;){
                if(mx[j]>=req+x){
                    dp[i]+=dp[j-1];
                    req=max(0ll,req-a[j]+x)<<1;
                } else {
                    req=max(0ll,req-a[j])<<1;
                }
            }
        }
    }
    return dp.back();
}

Compilation message (stderr)

biscuits.cpp: In function 'll count_tastiness(ll, std::vector<long long int>)':
biscuits.cpp:6:8: warning: unused variable 'ans' [-Wunused-variable]
    6 |     ll ans=0;
      |        ^~~

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