Submission #413778

#	Time	Username	Problem	Language	Result	Execution time	Memory
413778		Antekb	Holiday (IOI14_holiday)	C++14	100 / 100	3093 ms	7632 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, S2;//S-dobre, S2-reszta
//multiset<int> co;
ll sum=0;
void dodaj(int i){
	//cout<<"+ "<<i<<"\n";
	//co.insert(i);
	S.insert(tab[i]);
	sum+=tab[i];
}
void usun(int i){
	//cout<<"- "<<i<<"\n";
	//co.erase(co.find(i));
	if(S.find(tab[i])!=S.end()){
		sum-=tab[i];
		S.erase(S.find(tab[i]));
	}
	else S2.erase(S2.find(tab[i]));
}
/*void out(){
	cout<<co.size()<<"\n";
	for(int i:co)cout<<i<<" ";
	cout<<"\n";
}*/
int L=0, R=0;
void solve(int l, int r, int lopt, int ropt){
	//cout<<l<<" "<<r<<" "<<lopt<<" "<<ropt<<endl;
	//out();
	if(l>r) return;
	int m=(l+r+1)>>1;
	while(L>m)dodaj(--L);
	while(R<max(m, lopt))dodaj(R++);
	while(L<m)usun(L++);
	while(R>max(m, lopt))usun(--R);
	//cout<<L<<" "<<R<<"\n";
	/*for(int i=m; i<=r && i<lopt; i++){
		dodaj(i);
	}*/
	opt[m]=max(lopt, m);
	for(int i=opt[m]; i<=ropt; i++){
		dodaj(i);
		while(S.size()>max(0, d+2*m-s-i)){
			sum-=*S.begin();
			S2.insert(*S.begin());
			S.erase(S.begin());
		}
		while(S.size()<max(0, d+2*m-s-i) && S2.size()){
			sum+=*S2.crbegin();
			S.insert(*S2.crbegin());
			S2.erase(S2.find(*S2.crbegin()));
		}
		//cout<<m<<" "<<i<<" "<<sum<<"\n";
		if(sum>dp[m]){
			opt[m]=i;
			dp[m]=sum;
		}
	}
	R=ropt+1;
	/*for(int i=ropt; i>=opt[m]; i--){
		usun(i);
	}*/
	//cout<<m<<" "<<dp[m]<<" opt: "<<opt[m]<<endl;
	//for(int i=lopt; i<m; i++)usun(i);
	solve(l, m-1, lopt, opt[m]);
	//for(int i=m; i<opt[m] && i<=r; i++)usun(i);
	solve(m+1, r, opt[m], ropt);
}
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];
	solve(max(0, s-d), s, 0, 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];
    L=0, R=0;
    for(int i=0; i<n; i++)dp[i]=opt[i]=0;
    //co.clear();
    S.clear();
    S2.clear();
    sum=0;
    s=n-1-s;
    solve(max(0, s-d), s, 0, n-1);
	for(int i=0; i<=s; i++)ans=max(ans, dp[i]);
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:49:17: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   49 |   while(S.size()>max(0, d+2*m-s-i)){
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~
holiday.cpp:54:17: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   54 |   while(S.size()<max(0, d+2*m-s-i) && S2.size()){
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~

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