Submission #1031131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031131		happy_node	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1060 ms	18604 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

long long count_tastiness(long long X, std::vector<long long> a) {
	while(a.size()<60) a.push_back(0);
	int K=a.size();

	vector<pair<ll,ll>> dp;
	dp.push_back({0,1}); // (balance, distinct ways)

	for(int b=0;b<60;b++) {	
		vector<pair<ll,ll>> ndp;

		for(auto [x,y]:dp) {
			ndp.push_back({(x+a[b])/2,y}); // do nothing
			if(x+a[b]>=X)
				ndp.push_back({(x+a[b]-X)/2,y}); // create new stuff
		}

		sort(ndp.begin(),ndp.end());

		vector<pair<ll,ll>> nxt;

		for(int i=0;i<ndp.size();i++) {
			int j=i;
			ll sum=ndp[i].second;
			while(j+1<ndp.size() && ndp[j+1].first==ndp[j].first) j++, sum+=ndp[j].second;
			nxt.push_back({ndp[i].first,sum});
			i=j;
		}

		swap(dp,nxt);
	}

	ll sum=0;
	for(auto [x,y]:dp) sum+=y;

	return sum;
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int i=0;i<ndp.size();i++) {
      |               ~^~~~~~~~~~~
biscuits.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    while(j+1<ndp.size() && ndp[j+1].first==ndp[j].first) j++, sum+=ndp[j].second;
      |          ~~~^~~~~~~~~~~
biscuits.cpp:9:6: warning: unused variable 'K' [-Wunused-variable]
    9 |  int K=a.size();
      |      ^

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