oj.uz

Submission #706324

# Submission time Handle Problem Language Result Execution time Memory
706324 2023-03-06T09:29:21 Z jamezzz Holiday (IOI14_holiday) C++17
100 / 100
 1649 ms 6580 KB 
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
typedef long long ll;

#define maxn 100005

int n,s,d,a[maxn],cantake,lptr,rptr;
ll ans,sm;
multiset<ll> in,out;

void fix(){
	while(in.size()>cantake){
		auto it=in.begin();
		sm-=*it;
		out.insert(*it);
		in.erase(it);
	}
	while(in.size()<cantake&&!out.empty()){
		auto it=--out.end();
		sm+=*it;
		in.insert(*it);
		out.erase(it);
	}
}

void add(int x){
	sm+=x;
	in.insert(x);
	fix();
}

void rem(int x){
	if(out.find(x)!=out.end()){
		out.erase(out.find(x));
	}
	else{
		in.erase(in.find(x));
		sm-=x;
		fix();
	}
}

void dnc(int l,int r,int optl,int optr){
	if(l>r||optl>optr)return;
	int m=(l+r)>>1;
	while(lptr<m)rem(a[lptr++]);
	while(m<lptr)add(a[--lptr]);
	while(rptr<optl-1)add(a[++rptr]);
	while(optl-1<rptr)rem(a[rptr--]);
	fix();
	ll mx=-1;int best=0;
	for(int i=optl;i<=optr;++i){
		add(a[i]);
		cantake=max(d-(s-m+i-m),0);
		fix();
		if(sm>mx)best=i,mx=sm;
	}
	rptr=optr;
	ans=max(ans,mx);
	dnc(l,m-1,optl,best);
	dnc(m+1,r,best,optr);
}

void solve(){
	in.clear();out.clear();
	sm=cantake=0;
	lptr=1,rptr=s;
	for(int i=s;i>=1;--i){
		add(a[i]);
		cantake=max(d-(s-i),0);
		fix();
		ans=max(ans,sm);
	}
	dnc(1,s-1,s+1,n);
}

ll findMaxAttraction(int _n,int _s,int _d,int _a[]){
	n=_n,s=_s+1,d=_d;
	ans=0;
	for(int i=1;i<=n;++i)a[i]=_a[i-1];
	solve();
	reverse(a+1,a+n+1);
	s=n-s+1;
	solve();
	return ans;
}

Compilation message

holiday.cpp: In function 'void fix()':
holiday.cpp:15:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |  while(in.size()>cantake){
      |        ~~~~~~~~~^~~~~~~~
holiday.cpp:21:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |  while(in.size()<cantake&&!out.empty()){
      |        ~~~~~~~~~^~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 696 KB Output is correct
3 Correct 1 ms 696 KB Output is correct
4 Correct 1 ms 704 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 700 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5972 KB Output is correct
2 Correct 30 ms 5928 KB Output is correct
3 Correct 26 ms 5964 KB Output is correct
4 Correct 26 ms 5908 KB Output is correct
5 Correct 37 ms 5608 KB Output is correct
6 Correct 8 ms 2132 KB Output is correct
7 Correct 16 ms 3412 KB Output is correct
8 Correct 23 ms 3924 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 840 KB Output is correct
2 Correct 2 ms 872 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 17 ms 856 KB Output is correct
5 Correct 18 ms 848 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 5 ms 704 KB Output is correct
8 Correct 6 ms 696 KB Output is correct
9 Correct 6 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6580 KB Output is correct
2 Correct 37 ms 6564 KB Output is correct
3 Correct 420 ms 3188 KB Output is correct
4 Correct 16 ms 724 KB Output is correct
5 Correct 5 ms 744 KB Output is correct
6 Correct 5 ms 692 KB Output is correct
7 Correct 5 ms 696 KB Output is correct
8 Correct 1649 ms 5996 KB Output is correct
9 Correct 1553 ms 6004 KB Output is correct