Submission #129105

#	Time	Username	Problem	Language	Result	Execution time	Memory
129105		arthurconmy	Rice Hub (IOI11_ricehub)	C++14	0 / 100	6 ms	888 KiB

ricehub

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;

#ifndef ARTHUR_LOCAL
	#include "ricehub.h"
#endif

#ifdef ARTHUR_LOCAL
	#define ARTHUR_MAIN main
#endif

using ll = long long;

#define REP(i,a,b) \
for(int i=int(a); i<=int(b); i++)

#define len(x) int(x.size())

int besthub(int R, int L, int X[], long long B)
{
	ll cur_budget = B + R*0;
	int maxx=0;
	
	deque<int> ahead;

	REP(i,0,L-1) ahead.push_back(X[i]);

	deque<int> cur_behind;
	deque<int> cur_ahead;

	cur_behind.push_back(X[0]);
	ahead.pop_front();

	while(cur_budget>0 && !ahead.empty())
	{
		if(cur_budget >= ahead.front()-X[0])
		{
			cur_budget -= ahead.front()-X[0];

			// cout << X[0] << " " << ahead.front() << endl;

			cur_ahead.push_back(ahead.front());
			ahead.pop_front();
		}

		else break;
	}

	maxx=cur_behind.size()+cur_ahead.size();

	// cout << cur_behind.size() << " " << cur_ahead.size() << endl;

	REP(i,1,R-1)
	{
		cur_budget -= ll(len(cur_behind)-len(cur_ahead))*ll(X[i]-X[i-1]);
		
		// move X[i] from cur_ahead to cur_behind

		if(!cur_ahead.empty()) cur_ahead.pop_front();
		else ahead.pop_front();
		cur_behind.push_back(X[i]);

		while(cur_budget < 0) 
		{
			cur_budget += X[i]-cur_behind.front();
			cur_behind.pop_front();
		}

		while(cur_budget > 0 && !ahead.empty() && ahead.front()-X[i] <= cur_budget)
		{
			cur_budget -= ahead.front()-X[i];
			cur_ahead.push_back(ahead.front());
			ahead.pop_front();
		}

		while(!ahead.empty() && !cur_behind.empty() && ahead.front() - X[i] <= X[i] - cur_behind.front())
		{
			cur_budget -= X[i] + X[i] - cur_behind.front() - ahead.front();
			cur_behind.pop_front();
			cur_ahead.push_back(ahead.front());
			ahead.pop_front();

			while(cur_budget > 0 && !ahead.empty() && ahead.front()-X[i] <= cur_budget)
			{
				cur_budget -= ahead.front()-X[i];
				cur_ahead.push_back(ahead.front());
				ahead.pop_front();
			} // yikes a lot of while loops
		}

		maxx=max(maxx,len(cur_behind)+len(cur_ahead));

		// cout << X[i] << " " << len(cur_behind) << " " << len(cur_ahead) << endl;

		// cur_behind.push_front()
	}

	return maxx;
}

// int X[5];

// int ARTHUR_MAIN()
// {
// 	X[0]=1;
// 	X[1]=2;
// 	X[2]=10;
// 	X[3]=12;
// 	X[4]=14;

// 	cout << besthub(5,20,X,6) << endl;

// 	return 0;
// }

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