Submission #1203619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203619		shadow_sami	Holiday (IOI14_holiday)	C++20	24 / 100	5094 ms	1728 KiB

holiday

#include "holiday.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
#define ff first
#define ss second
#define fip(a,b) for(ll i = a ; i < b; i++)
#define fjp(a,b) for(ll j = a ; j < b; j++)
#define fp(k,a,b) for(ll k = a ; k < b; k++)
#define fin(a,b) for(ll i = a ; i >= b; i--)
#define fjn(a,b) for(ll j = a ; j >= b; j--)
#define fn(k,a,b) for(ll k = a ; k >= b; k--)
#define fx(a) for(auto x:a)
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define nli "\n"
#define test ll t;cin>>t;while(t--)

void _printn(int a){cerr<<a<<" ";}
void _printn(ll a){cerr<<a<<" ";}
void _printn(bool a){cerr<<a<<" ";}
void _printn(double a){cerr<<a<<" ";}

template<class T> void _printn(vector<T> a);
template<class T,class V> void _printn(pair<T,V> a);
template<class T> void _printn(vector<T> a){
	cerr<<"[  ";
	fx(a){
		_printn(x);cerr<<" ";
	}
	cerr<<"]";
}

template<class T,class V> void _printn(pair<T,V> a){
	cerr<<"( ";
	_printn(a.ff);
	cerr<<",";
	_printn(a.ss);
	cerr<<")";
}

auto cmp = [](ll aa,ll bb){
	return aa > bb;
};

priority_queue<ll,vector<ll>,decltype(cmp)> pq(cmp),pq2(cmp);

#ifdef SAMI
	#define debug(x) cerr<<#x<<" : ";_printn(x);cerr<<nli;
	#define debg() cerr<<nli;
	void deb(){
		pq2 = pq;
		while(pq2.size()){
			cerr<<pq2.top()<<" ";
			pq2.pop();
		}
		cerr<<nli;
	}
#else
	#define debug(x)
	#define debg()
	void deb(){
		return;
	}
#endif

const ll mx = 1e5 + 5;
const ll mod = 1e9 + 7;
bool f = 0;
ll n,m,res,cnt,sum,tp,tp2,tptp,ans;


long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	ans = -1e18;
	res = 0;
	sum = 0;
	fin(start,0){
		while(pq.size())pq.pop();
		sum = 0;
		fjn(start,i){
			sum += attraction[j];
			pq.push(attraction[j]);
			deb();
		}
		res = start - i;
		
		while(pq.size() > d-res){
			sum -= pq.top();
			pq.pop();
		}
		debug(d);
		debug(res);
		debug(i);
		debug(sum);
		deb();		
		if(d-res>=0)
			ans = max(ans,sum);
		fjp(start+1,n){
			sum += attraction[j];
			pq.push(attraction[j]);
			while(pq.size() > d-res-(j-i)){
				sum -= pq.top();
				pq.pop();
			}
			debug(res+(j-i))
			debug(j);
			debug(sum);
			deb();
			if(d-res-(j-i)>=0)
				ans = max(ans,sum);
		}
		debg();
	}
	fip(start,n){
		while(pq.size())pq.pop();
		sum = 0;
		fjp(start,i+1){
			sum += attraction[j];
			pq.push(attraction[j]);			

		}
		res = abs(start - i);		
		while(pq.size() > d-res){
			sum -= pq.top();
			pq.pop();
		}			
		if(d-res>=0)
			ans = max(ans,sum);
		fjn(start-1,0){
			sum += attraction[j];
			pq.push(attraction[j]);
			while(pq.size() > d-res-(i-j)){
				sum -= pq.top();
				pq.pop();
			}			
			if(d-res-(i-j)>=0)
				ans = max(ans,sum);
		}
		debg();
	}
    return ans;
}

#ifdef SAMI

int main() {	
	freopen("input1.txt","r",stdin);
	freopen("output1.txt","w",stdout);
	freopen("error1.txt","w",stderr);
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
	n_s = scanf("%d", &attraction[i]);
    }
    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
    return 0;
}
#endif

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