Submission #136531

#	Time	Username	Problem	Language	Result	Execution time	Memory
136531		nxteru	Holiday (IOI14_holiday)	C++14	100 / 100	1964 ms	19840 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
struct data{
	priority_queue<ll,vector<ll>,greater<ll>>u;
	priority_queue<ll>d;
	ll s,x;
	void ini(void){
		s=0,x=0;
		while(!u.empty())u.pop();
		while(!d.empty())d.pop();
	}
	void up(void){
		x++;
		while(ll(u.size())<x&&!d.empty()){
			s+=d.top();
			u.push(d.top());
			d.pop();
		}
	}
	void down(void){
		x--;
		while(!u.empty()&&x<ll(u.size())){
			s-=u.top();
			d.push(u.top());
			u.pop();
		}
	}
	void add(ll y){
		u.push(y);
		s+=y;
		s-=u.top();
		d.push(u.top());
		u.pop();
		x--;
		up();
	}
};
ll c[100005],a[250005],dp[250005],lo[250005],lt[250005],ro[250005],rt[250005];
data p;
bool vis[250005];
void calc(ll n,ll h,ll ans[],ll dy){
	for(int i=0;i<=h+1;i++)vis[i]=false;
	a[0]=0,a[h+1]=n;
	dp[0]=0,dp[h+1]=0;
	vis[0]=true,vis[h+1]=true;
	vector<ll>res;
	res.PB(0);
	res.PB(h+1);
	while(res.size()!=h+2){
		p.ini();
		ll e=0,d=0;
		for(int i=0;i+1<res.size();i++){
			ll m=(res[i]+res[i+1])/2;
			while(d<m){
				d++;
				p.up();
			}
			ll in=e,v=p.s;
			while(e<a[res[i+1]]){
				e++;
				p.add(c[e]);
				for(int j=0;j<dy;j++)p.down();
				if(v<p.s){
					v=p.s;
					in=e;
				}
			}
			a[m]=in;
			dp[m]=v;
			vis[m]=true;
		}
		res.clear();
		for(int i=0;i<=h+1;i++)if(vis[i])res.PB(i);
	}
	for(int i=0;i<=h;i++)ans[i]=dp[i];
}
ll findMaxAttraction(int n,int st,int d,int at[]){
	c[0]=0;
    int k=0;
    for(;st+k+1<n;){
		k++;
		c[k]=at[st+k];
	}
	calc(k,d,ro,1);
	calc(k,d,rt,2);
	k=0;
	for(;st-k-1>=0;){
		k++;
		c[k]=at[st-k];
	}
	calc(k,d,lo,1);
	calc(k,d,lt,2);
	for(int i=1;i<=d;i++){
		lo[i]=max(lo[i],lo[i-1]);
		ro[i]=max(ro[i],ro[i-1]);
		lt[i]=max(lt[i],lt[i-1]);
		rt[i]=max(rt[i],rt[i-1]);
	}
	ll ans=0;
	for(int i=0;i<=d;i++){
		ans=max(ans,lo[i]+rt[d-i]);
		ans=max(ans,ro[i]+lt[d-i]);
		if(i<d){
			ans=max(ans,lo[i]+rt[d-1-i]+ll(at[st]));
			ans=max(ans,ro[i]+lt[d-1-i]+ll(at[st]));
		}
	}
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void calc(ll, ll, ll*, ll)':
holiday.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(res.size()!=h+2){
        ~~~~~~~~~~^~~~~
holiday.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+1<res.size();i++){
               ~~~^~~~~~~~~~~

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