Submission #987691

#	Time	Username	Problem	Language	Result	Execution time	Memory
987691		AdamGS	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	68 ms	1368 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
ll count_tastiness(ll x, vector<ll>T) {
  while(T.size()<61) T.pb(0);
  vector<ll>sum(61), dp(61);
  sum[0]=T[0];
  for(ll i=1; i<61; ++i) sum[i]=sum[i-1]+(T[i]<<i);
  dp[0]=1;
  for(ll i=1; i<61; ++i) {
    ll p=1ll<<i; --p;
    for(ll j=i-1; j>=0; --j) {
      if(p&(1ll<<j)) {
        dp[i]+=dp[j];
        if(sum[j]/x+1<(1ll<<j)) {
          p=-1;
          break;
        }
        if(sum[j]-(1ll<<j)*x<0) {
          p=-1;
          break;
        }
        ll a=(sum[j]-(1ll<<j)*x)/x;
        if(j==0) a=0;
        else a=min(a, sum[j-1]/x);
        a=min(a, p-(1ll<<j));
        p=a;
      }
    }
    if(p==0) ++dp[i];
  }
  return dp[60];
}

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