Submission #237051

#	Time	Username	Problem	Language	Result	Execution time	Memory
237051		crossing0ver	Holiday (IOI14_holiday)	C++17	23 / 100	125 ms	5880 KiB

holiday

#include<bits/stdc++.h>
#include"holiday.h"
#define ll long long 
#define fi first
#define se second
using namespace std;
int n,x,d,val[100005];
ll solveR() {
	set <pair<int,int> >  s;
	ll eaten = 0,ans = val[x];
	int left = 0;
	eaten = val[x];
	s.insert({val[x],x});
	for (int i = x + 1; i < n; i++) {
		int stamina = i + s.size();
		if (i - x >= d) {left = i + 1; break;}
		while (stamina >= d) {
			eaten -= (*s.begin()).fi;
			s.erase(s.begin());
				stamina--;	
		}
		if (stamina < d) {
			eaten += val[i];
			s.insert({val[i],i});
		}
		ans = max(ans,eaten);
	}    
	return ans;				
}
ll solve() {
	set <pair<int,int> >  s;
	set <pair<int,int>,greater< pair<int,int> >  > g;
	ll eaten = 0,ans = val[x];
	int left = 0;
	for (int i = x; i >= 0; i--) {
		s.insert({val[i],i});
		eaten += val[i];
	}
	int l = 0;
	for (int i = x + 1; i < n && i < x + d; i++) {
		s.insert({val[i],i});
		eaten += val[i];
		 int stamina = (i - x + i - l) + s.size();
		 while (stamina > d) {
		 	if (i - x + i - l > d) {
		 		stamina--;
		 		if (s.find({val[l],l}) != s.end()) {
		 			stamina--;
		 			s.erase({val[l],l});
		 			eaten -= val[l];
				 }
		 		l++;
			}
			else {
				if (s.find({val[l],l}) == s.end() && l < x)  {
					l++;
					stamina--;
					continue;
				}
				int in = (*s.begin()).se;
				eaten -= (*s.begin()).fi;
				if (in == l && l < x) {
					l++;
					stamina-=2;
				}
				else 	{
				stamina--;
				g.insert(*s.begin());
			}
				s.erase(s.begin());
			}
		 }
		 if (stamina < d && g.size()) {
		 	s.insert(*g.begin());
		 	g.erase(g.begin());
		 }
		 ans = max(ans,eaten);
	}
	return ans;   				
}
long long int findMaxAttraction(int n1, int start, int d1, int attraction[]) {
	n = n1;
	x = start;
	d = d1;
	ll ans = 0;
	if (!d) return 0;
	if (d == 1) return val[start];
	for (int i = 0; i < n; i ++) val[i] = attraction[i];
	ans = max(ans,solveR());
	ans = max(ans,solve());
	for (int  i = 0 ;i  < n; i++) val[i] = attraction[n-i];
	x = n - x;
	ans = max(ans,solveR());
	ans = max(ans,solve());	
	return ans;
}       /* 
main(){
	freopen("read1.txt","r",stdin);
	freopen("write1.txt","w",stdout);
	int n,start,d;
	cin >> n >> start >> d;
	int att[n];
	for (int i  = 0; i < n ;i ++) cin >> att[i];
	cout << findMaxAttraction(n,start,d,att);
}              */
						  

Compilation message (stderr)

holiday.cpp: In function 'long long int solveR()':
holiday.cpp:11:6: warning: variable 'left' set but not used [-Wunused-but-set-variable]
  int left = 0;
      ^~~~
holiday.cpp: In function 'long long int solve()':
holiday.cpp:34:6: warning: unused variable 'left' [-Wunused-variable]
  int left = 0;
      ^~~~

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