Submission #1091929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091929		onlk97	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	53 ms	1468 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
map <long long,long long> dp;
vector <long long> ps;
long long X;
long long calc(long long u){
    if (u<=0) return 0;
    if (dp.find(u)!=dp.end()) return dp[u];
    long long g=__lg(u-1);
    dp[u]=calc(1ll<<g)+calc(min(u,ps[g]/X+1)-(1ll<<g));
    return dp[u];
}
long long count_tastiness(long long x,vector <long long> a){
    dp.clear();
    dp[1]=1;
    ps.clear();
    ps.push_back(a[0]);
    for (int i=1; i<a.size(); i++) ps.push_back(ps.back()+(a[i]<<i));
    while (ps.size()<=100) ps.push_back(ps.back());
    X=x;
    return calc(ps.back()/x+1);
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i=1; i<a.size(); i++) ps.push_back(ps.back()+(a[i]<<i));
      |                   ~^~~~~~~~~

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