oj.uz

Submission #152796

# Submission time Handle Problem Language Result Execution time Memory
152796 2019-09-09T14:30:27 Z junhopark Holiday (IOI14_holiday) C++14
0 / 100
 5000 ms 7800 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5068 ms 6972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4112 ms 1016 KB Output is correct
2 Correct 1978 ms 828 KB Output is correct
3 Correct 1984 ms 888 KB Output is correct
4 Incorrect 1419 ms 788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5046 ms 7800 KB Time limit exceeded
2 Halted 0 ms 0 KB -