Submission #1180962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180962		Pacybwoah	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	58 ms	948 KiB

biscuits

#include "biscuits.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include<iostream>
#include<vector>
#include<cassert>
#include<algorithm>
#include<utility>
#include<chrono>
#include<map>
#include<iomanip>
using namespace std;
typedef long long ll;
namespace{
	vector<ll> vec;
	map<ll, ll> m;
	int n;
	ll k;
	ll f(ll x){
		if(x < 0) return 0;
		if(x == 0) return 1;
		if(m.count(x)) return m[x];
		for(ll i = 0; i < n; i++){
			if(((1ll << i) <= x && (1ll << (i + 1)) > x)){
				ll res = f((1ll << i) - 1) + f(min(x, vec[i] / k) - (1ll << i));
				m[x] = res;
				return res;
			}
		}
	}
}

long long count_tastiness(ll K, std::vector<long long> a) {
	k = K;
	vec = a;
	while((int)vec.size() < 62) vec.push_back(0);
	n = (int)vec.size();
	map<ll, ll>().swap(m);
	for(int i = 0; i < n; i++) vec[i] <<= i;
	for(int i = 1; i < n; i++) vec[i] += vec[i - 1];
	return f(vec[n - 1]);
}

// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g biscuits.cpp grader.cpp

Compilation message (stderr)

biscuits.cpp: In function 'll {anonymous}::f(ll)':
biscuits.cpp:30:9: warning: control reaches end of non-void function [-Wreturn-type]
   30 |         }
      |         ^

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