Submission #413775

#	Time	Username	Problem	Language	Result	Execution time	Memory
413775		Antekb	Holiday (IOI14_holiday)	C++14	7 / 100	5094 ms	2552 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll dp[N], opt[N];
int tab[N];
int n, s, d;
multiset<int> S;//S-dobre, S2-reszta
ll sum=0;
void solve(int l, int r){
	opt[l]=l;
	for(int i=opt[l]; i<=r; i++){
		S.insert(tab[i]);
		sum=0;
		auto it=S.crbegin();
		int j=0;
		while(j<d+2*l-s-i && it!=S.crend()){
			sum+=*it;
			j++;
			it++;
		}
		//cout<<l<<" "<<i<<" "<<j<<"\n";
		if(sum>dp[l]){
			opt[l]=i;
			dp[l]=sum;
		}
	}
	S.clear();
}
long long int findMaxAttraction(int _n, int start, int _d, int attraction[]) {
	n=_n;
	d=_d;
	s=start;
	for(int i=0; i<n; i++)tab[i]=attraction[i];
	for(int i=0; i<=s; i++)solve(i, n-1);
	ll ans=0;
	for(int i=0; i<=s; i++)ans=max(ans, dp[i]);
    for(int i=0; i<n; i++)tab[i]=attraction[n-1-i];
    for(int i=0; i<n; i++)dp[i]=opt[i]=0;
    s=n-1-s;
    for(int i=0; i<=s; i++)solve(i, n-1);
	for(int i=0; i<=s; i++)ans=max(ans, dp[i]);
    return ans;
}

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