Submission #1014475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014475		biximo	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	3 ms	600 KiB

biscuits

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


long long count_tastiness(long long x, vector<long long> a) {
	
	int n = a.size();
	vector<array<long long,2>> dp[61];
	while(a.size() != 60) a.push_back(0);
	dp[a.size()].push_back({0,1});
	a.insert(a.begin(),0);
	for(int i = 1; i < a.size(); i ++) {
		a[i] = (1LL<<i-1)*a[i]+a[i-1];
	}
	for(int i = a.size()-1; i >= 1; i --) {
		sort(dp[i].begin(),dp[i].end());
		long long sum = 0;
		for(int p3 = 0, p2 = i; p3 < dp[i].size(); p3 ++) {
			if(p3+1<dp[i].size() && dp[i][p3+1][0] == dp[i][p3][0]) {
				dp[i][p3+1][1] += dp[i][p3][1];
				continue;
			}
			auto[p1,v] = dp[i][p3];
			sum += v;
			if(a[i]-p1 < (__int128)(1LL<<i-1)*x) continue;
			while(p2>0&&a[i]-a[p2-1]-p1<(1LL<<i-1)*x) p2 --;
			if(p2 < i)
			dp[p2].push_back({(1LL<<i-1)*x+p1-(a[i]-a[p2]),v});
			else sum += v;
		}
		dp[i-1].push_back({0,sum});
	}
	long long sum = 0;
	for(auto[a,v]: dp[0]) sum += v;
	return sum;

}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i = 1; i < a.size(); i ++) {
      |                 ~~^~~~~~~~~~
biscuits.cpp:14:17: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   14 |   a[i] = (1LL<<i-1)*a[i]+a[i-1];
      |                ~^~
biscuits.cpp:19:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(int p3 = 0, p2 = i; p3 < dp[i].size(); p3 ++) {
      |                           ~~~^~~~~~~~~~~~~~
biscuits.cpp:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |    if(p3+1<dp[i].size() && dp[i][p3+1][0] == dp[i][p3][0]) {
      |       ~~~~^~~~~~~~~~~~~
biscuits.cpp:26:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   26 |    if(a[i]-p1 < (__int128)(1LL<<i-1)*x) continue;
      |                                 ~^~
biscuits.cpp:27:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |    while(p2>0&&a[i]-a[p2-1]-p1<(1LL<<i-1)*x) p2 --;
      |                                      ~^~
biscuits.cpp:29:29: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   29 |    dp[p2].push_back({(1LL<<i-1)*x+p1-(a[i]-a[p2]),v});
      |                            ~^~
biscuits.cpp:8:6: warning: unused variable 'n' [-Wunused-variable]
    8 |  int n = a.size();
      |      ^

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