Submission #1174771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174771		khanhphucscratch	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	9 ms	860 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline bool getbit(int num, int bit)
{
    return (num >> bit)&1;
}
int count_tastiness(int x, vector<int> ad)
{
    vector<int> a;
    for(int i : ad) a.push_back(i);
    int k = 60; a.resize(k);
    vector<int> maxre(k);
    int sum = 0;
    for(int i = 0; i < k; i++){
        sum += (a[i] << i);
        maxre[i] = min((1ll << (i+1)), sum / x + 1);
    }
    vector<int> dp(k);
    dp[0] = maxre[0];
    for(int i = 1; i < k; i++){
        int re = maxre[i];
        for(int j = i-1; j >= 0; j--){
            int batch = (1ll << (j+1));
            if(re >= batch){
                dp[i] += dp[j];
                re -= batch;
            }
            re = min(re, maxre[j]);
        }
        dp[i] += re;
    }
    //for(int i = 0; i < 10; i++) cerr<<dp[i]<<" "<<maxre[i]<<endl;
    return dp[k-1];
}
/*signed main()
{
    int x, k;
    cin>>x>>k;
    vector<int> a(k);
    for(int i = 0; i < k; i++) cin>>a[i];
    cout<<count_tastiness(x, a);
}
*/

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