Submission #1059168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059168		mychecksedad	Packing Biscuits (IOI20_biscuits)	C++17	12 / 100	5 ms	600 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll __int128_t

long long count_tastiness(long long x, std::vector<long long> B) { vector<ll> a(all(B));
	// if(x > 1000000) return 1;
	int k = 63;
	a.resize(k);
	vector<vector<pair<ll, ll>>> dp(k);
	for(int i = 0; i + 1 < a.size(); ++i){
		if(a[i] > x){
			ll dif = (a[i] - x) / 2;
			a[i + 1] += dif;
			a[i] -= dif * 2;
		}
	}


	vector<ll> g(k);
	// k=63;
	g[0] = (a[0] >= x ? 2 : 1);
	// for(int i = 0; i < k; ++i) cout << a[i] << ' ';
	// cout << '\n';
	for(int i = 1; i < k; ++i){
		if(a[i] >= x){
			g[i] = g[i - 1] * 2;
		}else{
			g[i] = g[i - 1];
			ll sum = a[i] * 2, req = 2 * x;
			for(int j = i - 1; j >= 0; --j){
				ll add = min(a[j], req - sum);
				sum += add;
				// cout << j << ' ' << req << ' ' << sum << '\n';
				// cout << sum << ' ';
				if(sum >= req){
					g[i] += (j == 0 ? 1ll : g[j - 1]);
					sum -= req;
					req = x;
				}
				sum *= 2;
				req *= 2;
			}
		}
		// cout << g[i] << '\n';
	}
	return g.back();
}

Compilation message (stderr)

biscuits.cpp:11: warning: "ll" redefined
   11 | #define ll __int128_t
      | 
biscuits.cpp:5: note: this is the location of the previous definition
    5 | #define ll long long int
      | 
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<__int128>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i + 1 < a.size(); ++i){
      |                 ~~~~~~^~~~~~~~~~

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