Submission #782445

#	Time	Username	Problem	Language	Result	Execution time	Memory
782445		Lyrically	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	1 ms	556 KiB

boxes

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int read(){int x;scanf("%d",&x);return x;}
void print(int x){printf("%d\n",x);}
const int mod=1000000007;
long long delivery(int n,int k,int l,int p[])
{
	multiset<pii> ldis,rdis,all;
	rep(i,n)
	{
		if(p[i]<=l-p[i])
		{
			ldis.insert({p[i],0});all.insert({p[i],0});
		}
		else
		{
			rdis.insert({l-p[i],1});all.insert({l-p[i],1});
		}
	}
	long long res=0;
	while(!all.empty())
	{
		if((int)all.size()<k)
		{
			int ld=0,rd=0;
			for(auto v:all)
			{
				if(v.second==0){ld=max(ld,v.first);}
				else{rd=max(rd,v.first);}
			}
			res+=min(2*(ld+rd),l);break;
		}
		else
		{
			pii x=*(--all.end());
			all.erase(--all.end());
			int ld=0,rd=0;
			if(x.first*2>=l)
			{
				if(x.second==0){ldis.erase(x);ld=x.first;}
				else{rdis.erase(x);rd=x.first;}
				rep1(i,k-1)
				{
					pii y=*(--all.end());
					all.erase(--all.end());
					if(y.second==0){ldis.erase(y);ld=max(ld,y.first);}
					else{rdis.erase(y);rd=max(rd,y.first);}
				}
				res+=l;
			}
			else
			{
				if(x.second==0){ldis.erase(x);ld=x.first;}
				else{rdis.erase(x);rd=x.first;}
				int sz=k-1;
				if(!sz){res+=2*x.first;continue;}
				if(x.second==0&&!rdis.empty())
				{
					pii y=*(--rdis.end());all.erase(y);
					rdis.erase(y);
					rd=y.first;sz--;
				}
				else if(x.second==1&&!ldis.empty())
				{
					pii y=*(--ldis.end());all.erase(y);
					ldis.erase(y);
					ld=y.first;sz--;
				}
				rep1(i,sz)
				{
					pii y=*(--all.end());
					all.erase(--all.end());
					if(y.second==0){ldis.erase(y);ld=max(ld,y.first);}
					else{rdis.erase(y);rd=max(rd,y.first);}
				}
				res+=min(2*(ld+rd),l);
			}
		}
	}
	return res;
}

Compilation message (stderr)

boxes.cpp: In function 'int read()':
boxes.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | int read(){int x;scanf("%d",&x);return x;}
      |                  ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30