Submission #237029

#	Time	Username	Problem	Language	Result	Execution time	Memory
237029		crossing0ver	휴가 (IOI14_holiday)	C++17	0 / 100	97 ms	5844 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;
	for (int i = x; i >= 0; i--) {
		s.insert({i,val[i]});
		eaten += val[i];
	}
	int l = 0;
	for (int i = x + 1; i < n && i < x + d; 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 {
				int in = (*s.begin()).se;
				eaten -= (*s.begin()).fi;
				if (in == l) {
					l++;
					stamina-=2;
				}
				else 	stamina--;
				s.erase(s.begin());
			}
		 }
		 s.insert({val[i],i});
		 eaten += val[i];
		 ans = max(ans,eaten);
	}
	return ans;   				
}
ll solve() {
	set <pair<int,int> >  s;
	ll eaten = 0,ans = val[x];
	int left = 0;
	for (int i = x; i >= 0; i--) {
		s.insert({i,val[i]});
		eaten += val[i];
	}
	int l = 0;
	for (int i = x + 1; i < n && i < x + d; 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 {
				int in = (*s.begin()).se;
				eaten -= (*s.begin()).fi;
				if (in == l) {
					l++;
					stamina-=2;
				}
				else 	stamina--;
				s.erase(s.begin());
			}
		 }
		 s.insert({val[i],i});
		 eaten += val[i];
		 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;

}

Compilation message (stderr)

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

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