Submission #986411

#	Time	Username	Problem	Language	Result	Execution time	Memory
986411		Pyqe	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	37 ms	1448 KiB

biscuits

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n=60,a[60];
multiset<pair<long long,long long>> ms;
multiset<pair<long long,long long>>::iterator it;

void ins(long long x,long long w)
{
	multiset<pair<long long,long long>>::iterator it2=ms.lower_bound({x,0});
	
	if(it2!=ms.end()&&it2->fr==x)
	{
		w+=it2->sc;
		ms.erase(it2);
	}
	ms.insert({x,w});
}

long long count_tastiness(long long d,vector<long long> aa)
{
	long long i,k,w,sm,sz=aa.size();
	
	for(i=0;i<n;i++)
	{
		a[i]=0;
		if(i<sz)
		{
			a[i]=aa[i];
		}
		a[i]<<=i;
		if(i)
		{
			a[i]+=a[i-1];
		}
	}
	ms.clear();
	ins(-1,0);
	ins((1ll<<n)-1,1);
	for(i=n-1;i+1;i--)
	{
		a[i]=min(a[i]/d,(1ll<<i+1)-1);
		sm=0;
		for(it=prev(ms.end());it->fr>a[i];)
		{
			w=it->sc;
			sm+=w;
			it--;
			ms.erase(next(it));
		}
		ins(a[i],sm);
		sm=0;
		for(it=prev(ms.end());it->fr>(1ll<<i)-1;)
		{
			k=it->fr;
			w=it->sc;
			sm+=w;
			it--;
			ms.erase(next(it));
			ins(k^1ll<<i,w);
		}
		ins((1ll<<i)-1,sm);
	}
	return prev(ms.end())->sc;
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:48:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   48 |   a[i]=min(a[i]/d,(1ll<<i+1)-1);
      |                         ~^~

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