Submission #560526

#	Time	Username	Problem	Language	Result	Execution time	Memory
560526		AlperenT	Packing Biscuits (IOI20_biscuits)	C++17	21 / 100	1085 ms	8844 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>

using namespace std;

long long count_tastiness(long long x, vector<long long> arr){
	vector<pair<long long, long long>> prv, cur;
 
	while(!arr.empty() && arr.back() == 0) arr.pop_back();
 
	cur.push_back({0, 1});
 
	int k = 0;

	vector<long long> prefixsum(arr.size());

	prefixsum.back() = arr.back();

	for(int i = prefixsum.size() - 1; i >= 0; i--) prefixsum[i] = prefixsum[i + 1] + arr[i];
 
	while(true){
		bool flag = false;
		long long cnt = k < arr.size() ? arr[k] : 0, prefixcnt = k < arr.size() ? prefixsum[k] : 0;
 
		for(auto i : cur) if(i.first / 2 + prefixcnt - x >= 0) flag = true;
 
		if(flag){
			prv.clear();
 
			sort(cur.begin(), cur.end());
 
			for(auto p : cur){
				if(prv.empty() || (prv.back().first != p.first / 2)) prv.push_back({p.first / 2, p.second});
				else prv.back().second += p.second;
			}
 
			cur.clear();
 
			for(auto i : prv){
				cur.push_back({i.first + cnt, i.second});
				if(i.first + cnt - x >= 0) cur.push_back({i.first + cnt - x, i.second});
			}
		}
		else break;
 
		k++;
	}
 
	long long ans = 0;
 
	for(auto p : cur) ans += p.second;
 
	return ans;
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   long long cnt = k < arr.size() ? arr[k] : 0, prefixcnt = k < arr.size() ? prefixsum[k] : 0;
      |                   ~~^~~~~~~~~~~~
biscuits.cpp:23:62: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   long long cnt = k < arr.size() ? arr[k] : 0, prefixcnt = k < arr.size() ? prefixsum[k] : 0;
      |                                                            ~~^~~~~~~~~~~~

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