Submission #1065743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065743		n1k	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	1035 ms	197456 KiB

biscuits

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

using namespace std;
using ll = long long;

const int K = 61;

long long count_tastiness(long long x, std::vector<long long> a) {
	vector<ll> cnt(K+5);
	for(int i=0; i<a.size(); i++) cnt[i] = a[i];
	ll ans = 0;
	for(int i=0; i<K; i++){
		cnt[i+1] += max(0ll, (cnt[i]-x)/2);
	}
	//for(auto e:cnt) cerr<<e<<" "; cerr<<endl;
	vector<map<ll, ll>> dp(K+5);
	dp[0][0] = 1;
	for(int i=0; i<K; i++){
		for(auto [add, val]:dp[i]){
			ll have = cnt[i] + add;
			// take
			if(have >= x){
				dp[i+1][(have - x) / 2] += val;
			}
			dp[i+1][have/2] += val;
		}
	}
	for(auto [k, v]:dp[K]) {
		//cerr<<k<<" "<<v<<endl;
		ans+=v;
	}
	return ans;
}

/*
1
4 1
1 1 1 3
*/

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:11:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i=0; i<a.size(); i++) cnt[i] = a[i];
      |               ~^~~~~~~~~

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