Submission #152796

#	Time	Username	Problem	Language	Result	Execution time	Memory
152796		junhopark	Holiday (IOI14_holiday)	C++14	0 / 100	5068 ms	7800 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define all(V) (V).begin(),(V).end()
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 3e5+5;
int n, s, d, val[SZ];
LL ans, sum, dp[SZ], dp2[SZ];
multiset<LL> st;
multiset<LL>::iterator it;
void dnc(int si, int ei, int sp, int ep)
{
	if (si>ei||sp>ep) return;
	int mi=si+ei>>1, pl; //시간 mi, 가장 오른쪽 점 sp~ep
	st.clear();
	sum=0;
	for (int i=s+1; i<sp; i++) {
		st.insert(val[i]);
		sum+=val[i];
	}
	for (int i=sp; i<=ep; i++) {
		st.insert(val[i]);
		sum+=val[i];
		while ((int)st.size()>mi-(i-s)&&st.size()) {
			it=st.begin();
			sum-=*it;
			st.erase(it);
		}
		if (dp[mi]<sum) {
			pl=i;
			dp[mi]=sum;
		}
	}
	dnc(si,mi-1,sp,pl);
	dnc(mi+1,ei,pl,ep);
}
void dnc2(int si, int ei, int sp, int ep)
{
	if (si>ei||sp>ep) return;
	int mi=si+ei>>1, pl; //시간 mi, 가장 오른쪽 점 sp~ep
	st.clear();
	sum=0;
	for (int i=s; i>ep; i--) {
		st.insert(val[i]);
		sum+=val[i];
	}
	for (int i=ep; i>=sp; i--) {
		st.insert(val[i]);
		sum+=val[i];
		while ((int)st.size()>mi-(s-i)*2&&st.size()) {
			it=st.begin();
			sum-=*it;
			st.erase(it);
		}
		if (dp2[mi]<sum) {
			pl=i;
			dp2[mi]=sum;
		}
	}
	dnc2(si,mi-1,pl,ep);
	dnc2(mi+1,ei,sp,pl);
}
void solve()
{
	for (int i=0; i<=d; i++) dp[i]=dp2[i]=0;
	st.clear();
	dnc(1, d, s+1, n-1);
	dnc2(1, d, 0, s);
	for (int i=0; i<=d; i++) ans=max(ans,dp[i]+dp2[d-i]);
}
LL findMaxAttraction(int N, int start, int D, int attraction[])
{
	int i;
	n=N,s=start,d=D;
    for (i=0; i<n; i++) val[i]=attraction[i];
    solve();
    reverse(val,val+n);
    s=n-s-1;
    solve();
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void dnc(int, int, int, int)':
holiday.cpp:18:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mi=si+ei>>1, pl; //시간 mi, 가장 오른쪽 점 sp~ep
         ~~^~~
holiday.cpp: In function 'void dnc2(int, int, int, int)':
holiday.cpp:44:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mi=si+ei>>1, pl; //시간 mi, 가장 오른쪽 점 sp~ep
         ~~^~~
holiday.cpp: In function 'void dnc(int, int, int, int)':
holiday.cpp:38:5: warning: 'pl' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dnc(si,mi-1,sp,pl);
  ~~~^~~~~~~~~~~~~~~
holiday.cpp: In function 'void dnc2(int, int, int, int)':
holiday.cpp:64:6: warning: 'pl' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dnc2(si,mi-1,pl,ep);
  ~~~~^~~~~~~~~~~~~~~

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