Submission #199792

#	Time	Username	Problem	Language	Result	Execution time	Memory
199792		aer0park	Rice Hub (IOI11_ricehub)	C++14	32 / 100	27 ms	2680 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
#define f first
#define s second
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
 
ll sum,anw,cnt=1;
queue<ll> st,ed;

int besthub(int r,int l,int x[],ll b)
{
	for(int i=r;i>=1;i--)
		x[i]=x[i-1];
	x[r+1]=l+1;
	for(int i=1;i<=r;i++)
	{
		sum+=(st.size()-ed.size())*(x[i]-x[i-1]);
		if(!ed.empty()) st.push(ed.front()),ed.pop();
		else st.push(cnt),cnt++;
		if(sum<=b) anw=max(anw,(ll)st.size()+(ll)ed.size());
		while(st.size()>=2&&(sum>b||x[i]-x[st.front()]>=x[cnt]-x[i]))
			sum-=x[i]-x[st.front()],st.pop();
		while(cnt<=r&&sum+x[cnt]-x[i]<=b)
			ed.push(cnt),sum+=x[cnt]-x[i],cnt++;
		anw=max(anw,(ll)st.size()+(ll)ed.size());
	}
	return anw;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 32 / 32