Submission #115458

#	Time	Username	Problem	Language	Result	Execution time	Memory
115458		faustaadp	Holiday (IOI14_holiday)	C++17	47 / 100	549 ms	3064 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,x,i,j,ki[8080],ka[8080],a[101010],has;
long long int findMaxAttraction(int N, int start, int D, int attraction[]) 
{
	n=N;
	x=start;
	for(i=0;i<n;i++)
		a[i]=attraction[i];
	if(x==0)
	{
		ll hz=0,sz=0;
		priority_queue<ll> pq;
		for(i=0;i<min(n,(ll)D);i++)
		{
			pq.push(-a[i]);
			hz+=a[i];
			sz++;
			while(sz>(D-i))
			{
				sz--;
				hz+=pq.top();
				pq.pop();
			}
			has=max(has,hz);
		}
		return has;
	}
	for(i=x+1;i<n;i++)
	{
		vector<ll> tem;
		for(j=x+1;j<=i;j++)
			tem.pb(a[j]);
		sort(tem.begin(),tem.end());
		reverse(tem.begin(),tem.end());
		ll hz=0;
		for(j=0;j<tem.size();j++)
		{
			hz+=tem[j];
			ka[j+(i-x)+1]=max(ka[j+(i-x)+1],hz);
		}
	}
	for(i=x-1;i>=0;i--)
	{
		vector<ll> tem;
		for(j=x-1;j>=i;j--)
			tem.pb(a[j]);
		sort(tem.begin(),tem.end());
		reverse(tem.begin(),tem.end());
		ll hz=0;
		for(j=0;j<tem.size();j++)
		{
			hz+=tem[j];
			ki[j+(x-i)+1]=max(ki[j+(x-i)+1],hz);
		}
	}
	for(i=1;i<=D;i++)
	{
		ki[i]=max(ki[i-1],ki[i]);
		ka[i]=max(ka[i-1],ka[i]);
	}
	has=max(has,ki[D]);
	has=max(has,ka[D]);
	if(D>1)
		has=max(has,ki[D-1]+a[x]);
	if(D>1)
		has=max(has,ka[D-1]+a[x]);
	for(i=x+1;i<n;i++)
	{
		vector<ll> tem;
		for(j=x+1;j<=i;j++)
			tem.pb(a[j]);
		sort(tem.begin(),tem.end());
		reverse(tem.begin(),tem.end());
		ll hz=0;
		for(j=0;j<tem.size();j++)
		{
			hz+=tem[j];
			ll sisa=D-((i-x)*2+(j+1));
			if(sisa>=0)
				has=max(has,ki[sisa]+hz);
			if(sisa>=1)
				has=max(has,ki[sisa-1]+hz+a[x]);
		}
	}
	for(i=x-1;i>=0;i--)
	{
		vector<ll> tem;
		for(j=x-1;j>=i;j--)
			tem.pb(a[j]);
		sort(tem.begin(),tem.end());
		reverse(tem.begin(),tem.end());
		ll hz=0;
		for(j=0;j<tem.size();j++)
		{
			hz+=tem[j];
			ll sisa=D-((x-i)*2+(j+1));
			if(sisa>=0)
				has=max(has,ka[sisa]+hz);
			if(sisa>=1)
				has=max(has,ka[sisa-1]+hz+a[x]);
		}
	}
	// for(i=0;i<=D;i++)
	// 	cout<<i<<" "<<ki[i]<<"\n";
	// for(i=0;i<=D;i++)
	// 	cout<<i<<" "<<ka[i]<<"\n";
    return has;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:43:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tem.size();j++)
           ~^~~~~~~~~~~
holiday.cpp:57:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tem.size();j++)
           ~^~~~~~~~~~~
holiday.cpp:82:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tem.size();j++)
           ~^~~~~~~~~~~
holiday.cpp:100:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tem.size();j++)
           ~^~~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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