Submission #97507

#	Time	Username	Problem	Language	Result	Execution time	Memory
97507		MvC	Holiday (IOI14_holiday)	C++11	47 / 100	59 ms	6268 KiB

holiday

#pragma GCC optimize("O3")
#include "holiday.h"
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
ll f[nmax],rf[nmax],rg[nmax],g[nmax];
multiset<ll>st;
multiset<ll>::iterator it;
ll findMaxAttraction(int n,int s,int d,int a[])
{
	int i,v,j;
	ll sum,ans=0;
	if(n<=3000)
	{
		for(i=s;i>=0;i--)
		{
			st.in(a[i]);
			it=st.end();
			it--;
			sum=v=0;
			for(j=1;j+s-i<=d;j++)
			{
				if(!v)sum+=1LL*(*it);
				if(it!=st.begin())it--;
				else v=1;
				f[s-i+j]=max(f[s-i+j],sum);
				if(2*(s-i)+j<=d)g[2*(s-i)+j]=max(g[2*(s-i)+j],f[s-i+j]);
				if(v)break;
			}
		}
		st.clear();
		for(i=s+1;i<n;i++)
		{
			st.in(a[i]);
			it=st.end();
			it--;
			sum=v=0;
			for(j=1;j+i-s<=d;j++)
			{
				if(!v)sum+=1LL*(*it);
				if(it!=st.begin())it--;
				else v=1;
				rf[i-s+j]=max(rf[i-s+j],sum);
				if(2*(i-s)+j<=d)rg[2*(i-s)+j]=max(rg[2*(i-s)+j],rf[i-s+j]);
				if(v)break;
			}
		}
		for(i=1;i<=d;i++)
		{
			f[i]=max(f[i],f[i-1]);
			g[i]=max(g[i],g[i-1]);
			rf[i]=max(rf[i-1],rf[i]);
			rg[i]=max(rg[i-1],rg[i]);
		}
		for(i=0;i<=d;i++)ans=max(ans,max(f[i]+rg[d-i],g[i]+rf[d-i]));
	}
	else
	{
		for(i=0;i<n;i++)
		{
			st.in(a[i]);
			sum+=a[i];
			while(st.size()>d-i)
			{
				sum-=(*st.begin());
				st.er(st.begin());
			}
			ans=max(ans,sum);
		}
	}
	return ans;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	
    return 0;
}*/

Compilation message (stderr)

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(st.size()>d-i)
          ~~~~~~~~~^~~~
holiday.cpp:75:7: warning: 'sum' may be used uninitialized in this function [-Wmaybe-uninitialized]
    sum+=a[i];
    ~~~^~~~~~
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