Submission #338811

#	Time	Username	Problem	Language	Result	Execution time	Memory
338811		alishahali1382	Holiday (IOI14_holiday)	C++14	47 / 100	5069 ms	4664 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

ll ans; // :))
int n, start, D, k, u, v, x, y, t, a, b;
int A[MAXN];

struct Set{
	ll sum, sz;
	int mark[MAXN];
	priority_queue<pii, vector<pii>, greater<pii>> X;
	priority_queue<pii> Y;
	inline void relax(){
		while (X.size() && mark[X.top().second]!=1) X.pop();
		while (Y.size() && mark[Y.top().second]!=2) Y.pop();
	}
	void Add(int i){
		relax();
		int y=-inf, x=inf;
		if (X.size()) x=X.top().first;
		if (Y.size()) y=Y.top().first;
		if (A[i]<=x) mark[i]=2, Y.push({A[i], i});
		else mark[i]=1, X.push({A[i], i}), sum+=A[i], sz++;
	}
	void Rem(int i){
		if (mark[i]==1) sum-=A[i], sz--;
		mark[i]=0;
		relax(); // not necessary
	}
	ll Get(int k){
		if (k<0) return -INF;
		while (sz<k && Y.size()){
			int i=Y.top().second;
			Y.pop();
			if (mark[i]!=2) continue ;
			mark[i]=1;
			X.push({A[i], i});
			sum+=A[i];
			sz++;
		}
		while (sz>k){
			int i=X.top().second;
			X.pop();
			if (mark[i]!=1) continue ;
			mark[i]=2;
			Y.push({A[i], i});
			sum-=A[i];
			sz--;
		}
		return sum;
	}
} S;

ll findMaxAttraction(int nn, int starttt, int d, int attraction[]){
	n=nn;
	D=d;
	start=starttt;
	for (int i=0; i<n; i++) A[i]=attraction[i];
	for (int i=start; ~i; i--){
		S.Add(i);
		ans=max(ans, S.Get(D-(start-i)));
		for (int j=start+1; j<n; j++){
			S.Add(j);
			int a=start-i, b=j-start;
			ans=max(ans, S.Get(D-(a+b+min(a, b))));
		}
		for (int j=start+1; j<n; j++) S.Rem(j);
	}
	
	
	return ans;
}

Compilation message (stderr)

holiday.cpp: In member function 'void Set::Add(int)':
holiday.cpp:41:7: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   41 |   int y=-inf, x=inf;
      |       ^

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