Submission #305864

#	Time	Username	Problem	Language	Result	Execution time	Memory
305864		junseo	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	13 ms	928 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define rmin(r, x) r = min(r, x)
#define rmax(r, x) r = max(r, x)
#define ends ' '
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int maxk = 65;
const int maxa = 2e5 + 10;
 
bool p;
ll r[maxk], c[maxk];
 
ll get_r(ll T) {
	if(!T)		return 1;
	if(T == 1)	return 1 + p;
	int i = 63 - __builtin_clzll(T);
	return c[i - 1] + min(r[i] + 1, get_r(T - (1LL << i)));
}
 
long long count_tastiness(long long x, vector<ll> s) {
	int k = s.size();
	s.resize(maxk);
	for(int i = 1; i <= 60; ++i)	s[i] = s[i - 1] + (1LL << i) * s[i];
	
	p = (s[0] >= x);
	r[0] = p - 1;
	c[0] = p + 1;
 
	for(int i = 1; i <= 60; ++i) {
		ll T = s[i] / x - (1LL << i);
		if(T < 0) 		r[i] = -1;
		else {
			if((1LL << i) - 1 <= T)	r[i] = c[i - 1] - 1;
			else			r[i] = get_r(T) - 1;
		}
		c[i] = c[i - 1] + r[i] + 1;
	}
	return c[60];
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:31:6: warning: unused variable 'k' [-Wunused-variable]
   31 |  int k = s.size();
      |      ^

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