Submission #358593

#	Time	Username	Problem	Language	Result	Execution time	Memory
358593		Jasiekstrz	Packing Biscuits (IOI20_biscuits)	C++17	21 / 100	1103 ms	128068 KiB

biscuits

#include "biscuits.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int K=60;
long long count_tastiness(long long x,vector<long long> a)
{
	vector<pair<long long,long long>> t[61];
	vector<long long> p[61];
	int i;
	while(a.size()<=K)
		a.push_back(0);
	if(a[0]<x)
	{
		t[0]={{0,0},{a[0]+1,1}};
		p[0]={1,0};
	}
	else
	{
		t[0]={{0,0},{a[0]-x+1,1},{a[0]+1,1}};
		p[0]={2,1,0};
	}
	for(i=1;i<K;i++)
	{
		vector<pair<long long,long long>> tmp;
		for(auto v:t[i-1])
		{
			tmp.push_back({a[i]+(v.fi+1)/2,v.se});
			if(a[i]-x+(v.fi+1)/2>0)
				tmp.push_back({a[i]-x+(v.fi+1)/2,v.se});
		}
		tmp.push_back({0,0});
		sort(tmp.begin(),tmp.end());
		for(unsigned j=0;j<tmp.size();)
		{
			t[i].push_back({tmp[j].fi,0});
			for(;j<tmp.size() && tmp[j].fi==t[i].back().fi;j++)
				t[i].back().se+=tmp[j].se;
		}
		//cerr<<i<<"\n";
		//for(auto v:t[i])
		//	cerr<<v.fi<<","<<v.se<<" ";
		//cerr<<"\n";
		p[i].resize(t[i].size());
		p[i].back()=0;
		for(int j=t[i].size()-2;j>=0;j--)
		{
			//cerr<<j<<" "<<p[i].size()<<" "<<t[i].size()<<"\n";
			p[i][j]=p[i][j+1]+t[i][j+1].se;
		}
	}
	return p[K-1][0];
}

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