Submission #18104

#	Time	Username	Problem	Language	Result	Execution time	Memory
18104		comet	Holiday (IOI14_holiday)	C++98	0 / 100	5000 ms	6212 KiB

holiday

#include "holiday.h"
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pp;
typedef priority_queue<pp> pq;

int st;
ll a[100000];
ll b[100000];

bool chk[100000];

void f(int j,int i,int cnt){
	pq Q;
	for(int k=j;k<=i;k++){
		Q.push(pp(a[k],k));
	}
	
	ll sum=0,base=0;
	while(!Q.empty()){
		int v=Q.top().second;Q.pop();
		if(v<j)continue;
		if(cnt==0){
			cnt+=2;
			if(chk[j])chk[j]=0,base+=a[j];
			j++;
			if(j>st)break;
		}
		sum+=a[v];
		chk[v]=1;
		cnt--;
		b[i]=max(b[i],sum-base);
	}
}

void f2(int j,int i,int cnt){
	pq Q;
	for(int k=i;k<=j;k++){
		Q.push(pp(a[k],k));
	}
	
	ll sum=0,base=0;
	while(!Q.empty()){
		int v=Q.top().second;Q.pop();
		if(j<v)continue;
		if(cnt==0){
			cnt+=2;
			if(chk[j])chk[j]=0,base+=a[j];
			j--;
			if(j<st)break;
		}
		sum+=a[v];
		chk[v]=1;
		cnt--;
		b[i]=max(b[i],sum-base);
	}
}

ll findMaxAttraction(int n, int start, int d, int attraction[]){

	st=start;

	for(int i=0;i<n;i++){
		a[i]=attraction[i];
	}

	for(int i=start;i<n;i++){
		int x=i-start;
		int j=max(0,start-(d-x)/2);
		int y=start-j;
		int cnt=d-x-2*y;
		f(j,i,cnt);
	}

	for(int i=start;i>=0;i--){
		int x=start-i;
		int j=min(n-1,start+(d-x)/2);
		int y=j-start;
		int cnt=d-x-2*y;
		f2(j,i,cnt);
	}

	ll ans=0;

	for(int i=0;i<n;i++)ans=max(ans,b[i]);

	return ans;
}

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