oj.uz

답안 #136531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136531 2019-07-25T12:27:22 Z nxteru 휴가 (IOI14_holiday) C++14
100 / 100
 1964 ms 19840 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
struct data{
	priority_queue<ll,vector<ll>,greater<ll>>u;
	priority_queue<ll>d;
	ll s,x;
	void ini(void){
		s=0,x=0;
		while(!u.empty())u.pop();
		while(!d.empty())d.pop();
	}
	void up(void){
		x++;
		while(ll(u.size())<x&&!d.empty()){
			s+=d.top();
			u.push(d.top());
			d.pop();
		}
	}
	void down(void){
		x--;
		while(!u.empty()&&x<ll(u.size())){
			s-=u.top();
			d.push(u.top());
			u.pop();
		}
	}
	void add(ll y){
		u.push(y);
		s+=y;
		s-=u.top();
		d.push(u.top());
		u.pop();
		x--;
		up();
	}
};
ll c[100005],a[250005],dp[250005],lo[250005],lt[250005],ro[250005],rt[250005];
data p;
bool vis[250005];
void calc(ll n,ll h,ll ans[],ll dy){
	for(int i=0;i<=h+1;i++)vis[i]=false;
	a[0]=0,a[h+1]=n;
	dp[0]=0,dp[h+1]=0;
	vis[0]=true,vis[h+1]=true;
	vector<ll>res;
	res.PB(0);
	res.PB(h+1);
	while(res.size()!=h+2){
		p.ini();
		ll e=0,d=0;
		for(int i=0;i+1<res.size();i++){
			ll m=(res[i]+res[i+1])/2;
			while(d<m){
				d++;
				p.up();
			}
			ll in=e,v=p.s;
			while(e<a[res[i+1]]){
				e++;
				p.add(c[e]);
				for(int j=0;j<dy;j++)p.down();
				if(v<p.s){
					v=p.s;
					in=e;
				}
			}
			a[m]=in;
			dp[m]=v;
			vis[m]=true;
		}
		res.clear();
		for(int i=0;i<=h+1;i++)if(vis[i])res.PB(i);
	}
	for(int i=0;i<=h;i++)ans[i]=dp[i];
}
ll findMaxAttraction(int n,int st,int d,int at[]){
	c[0]=0;
    int k=0;
    for(;st+k+1<n;){
		k++;
		c[k]=at[st+k];
	}
	calc(k,d,ro,1);
	calc(k,d,rt,2);
	k=0;
	for(;st-k-1>=0;){
		k++;
		c[k]=at[st-k];
	}
	calc(k,d,lo,1);
	calc(k,d,lt,2);
	for(int i=1;i<=d;i++){
		lo[i]=max(lo[i],lo[i-1]);
		ro[i]=max(ro[i],ro[i-1]);
		lt[i]=max(lt[i],lt[i-1]);
		rt[i]=max(rt[i],rt[i-1]);
	}
	ll ans=0;
	for(int i=0;i<=d;i++){
		ans=max(ans,lo[i]+rt[d-i]);
		ans=max(ans,ro[i]+lt[d-i]);
		if(i<d){
			ans=max(ans,lo[i]+rt[d-1-i]+ll(at[st]));
			ans=max(ans,ro[i]+lt[d-1-i]+ll(at[st]));
		}
	}
	return ans;
}

Compilation message

holiday.cpp: In function 'void calc(ll, ll, ll*, ll)':
holiday.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(res.size()!=h+2){
        ~~~~~~~~~~^~~~~
holiday.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+1<res.size();i++){
               ~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 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 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 556 ms 16556 KB Output is correct
2 Correct 442 ms 16548 KB Output is correct
3 Correct 549 ms 16536 KB Output is correct
4 Correct 438 ms 16508 KB Output is correct
5 Correct 1382 ms 11232 KB Output is correct
6 Correct 610 ms 13488 KB Output is correct
7 Correct 846 ms 7836 KB Output is correct
8 Correct 918 ms 8020 KB Output is correct
9 Correct 458 ms 16448 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 1016 KB Output is correct
2 Correct 12 ms 1016 KB Output is correct
3 Correct 25 ms 1016 KB Output is correct
4 Correct 30 ms 760 KB Output is correct
5 Correct 27 ms 744 KB Output is correct
6 Correct 7 ms 504 KB Output is correct
7 Correct 6 ms 380 KB Output is correct
8 Correct 6 ms 420 KB Output is correct
9 Correct 7 ms 376 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 576 ms 19840 KB Output is correct
2 Correct 1964 ms 19284 KB Output is correct
3 Correct 300 ms 2004 KB Output is correct
4 Correct 18 ms 504 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 7 ms 376 KB Output is correct
8 Correct 1246 ms 5996 KB Output is correct
9 Correct 1245 ms 5972 KB Output is correct