Submission #304799

#	Time	Username	Problem	Language	Result	Execution time	Memory
304799		junseo	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	2 ms	384 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)
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2")
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;

ll r[maxk], c[maxk];

ll get_r(ll T) {
	if(!T)		return 0;
	if(T == 1)	return r[0];
	int i = 63 - __builtin_clzll(T);
	return c[i - 1] - 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];
	
	r[0] = (s[0] >= x) - 1;
	c[0] = r[0] + 1;

	for(int i = 1; i <= 60; ++i) {
		ll T = s[i] / x - (1LL << i);;
		if(T < 0) {
			r[i] = -1;
		}
		else {
			int j = 63 - __builtin_clzll(T);
			if(i <= j)	r[i] = c[i - 1] - 1;
			else		r[i] = get_r(T);
		}
		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:32:6: warning: unused variable 'k' [-Wunused-variable]
   32 |  int k = s.size();
      |      ^

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