Submission #399873

#	Time	Username	Problem	Language	Result	Execution time	Memory
399873		Jasiekstrz	Holiday (IOI14_holiday)	C++17	100 / 100	4844 ms	25592 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
multiset<int> not_used,used;
long long curr=0;
void pop_t()
{
	not_used.insert(*used.begin());
	curr-=(*used.begin());
	used.erase(used.begin());
	return;
}
void push_t()
{
	used.insert(*prev(not_used.end()));
	curr+=(*prev(not_used.end()));
	not_used.erase(prev(not_used.end()));
	return;
}
void dc(int dl,int dr,int attraction[],int s,int l,int r,vector<long long> &ans,int c)
{
	if(dl>dr)
		return;
	// solving for mid
	int dmid=(dl+dr)/2;
	while(c*(l-s)+used.size()>dmid)
		pop_t();
	while(c*(l-s)+used.size()<dmid)
		push_t();
	int gg=l;
	ans[dmid]=curr;
	for(int i=l+1;i<r;i++)
	{
		for(int it=1;it<=c && !used.empty();it++)
			pop_t();
		if(!used.empty())
		{
			pop_t();
			not_used.insert(attraction[i]);
			push_t();
			if(curr>ans[dmid])
			{
				ans[dmid]=curr;
				gg=i;
			}
		}
		else
			not_used.insert(attraction[i]);
	}
	// cleaning and recursive calls
	for(int i=r-1;i>l;i--)
	{
		if(not_used.find(attraction[i])!=not_used.end())
			not_used.erase(not_used.find(attraction[i]));
		else
		{
			curr-=attraction[i];
			used.erase(used.find(attraction[i]));
		}
	}
	dc(dl,dmid-1,attraction,s,l,gg+1,ans,c);
	for(int i=l+1;i<=gg;i++)
		not_used.insert(attraction[i]);
	dc(dmid+1,dr,attraction,s,gg,r,ans,c);
	for(int i=gg;i>l;i--)
	{
		if(not_used.find(attraction[i])!=not_used.end())
			not_used.erase(not_used.find(attraction[i]));
		else
		{
			curr-=attraction[i];
			used.erase(used.find(attraction[i]));
		}
	}
	return;
}
long long findMaxAttraction(int n,int start,int d,int attraction[])
{
	vector<long long> ans[2][2];
	for(int i:{0,1})
	{
		for(int j:{0,1})
		{
			ans[i][j].resize(d+10);
			fill(ans[i][j].begin(),ans[i][j].end(),0);
		}
	}
	for(int i=1;i<=d;i++)
		not_used.insert(0);
	for(int rev:{0,1})
	{
		if(start==n-1)
		{
			for(int i=1;i<=d;i++)
				ans[rev][0][i]=ans[rev][1][i]=attraction[n-1];
		}
		else
		{
			not_used.insert(attraction[start]);
			dc(0,d,attraction,start,start,n,ans[rev][0],1);
			dc(0,d,attraction,start,start,n,ans[rev][1],2);
			while(!used.empty())
				pop_t();
			not_used.erase(not_used.find(attraction[start]));
		}
		reverse(attraction,attraction+n);
		start=n-1-start;
		attraction[start]=0;
	}
	long long w=max(ans[0][0][d],ans[1][0][d]);
	for(int i=0;i<=d;i++)
		w=max({w,ans[0][1][i]+ans[1][0][d-i],ans[0][0][i]+ans[1][1][d-i]});
	return w;
}

Compilation message (stderr)

holiday.cpp: In function 'void dc(int, int, int*, int, int, int, std::vector<long long int>&, int)':
holiday.cpp:28:27: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |  while(c*(l-s)+used.size()>dmid)
      |        ~~~~~~~~~~~~~~~~~~~^~~~~
holiday.cpp:30:27: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  while(c*(l-s)+used.size()<dmid)
      |        ~~~~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53