Submission #129235

#	Time	Username	Problem	Language	Result	Execution time	Memory
129235		arthurconmy	Rice Hub (IOI11_ricehub)	C++14	49 / 100	23 ms	1656 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(ll i=int(a); i<=ll(b); i++)

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

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

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

	deque<ll> cur_behind;
	deque<ll> cur_ahead;

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

	while(cur_budget>0 && !ahead.empty()) // add as many rices as we can
	{
		if(cur_budget >= ahead.front()-ll(X[0]))
		{
			cur_budget -= ahead.front()-ll(X[0]);

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

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

		else break;
	}

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

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

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

		// cout << "THE CURRENT BUDGET IS " << cur_budget << " " << cur_behind.size() << endl;
		
		// 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(ll(X[i])); 

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

			// cout << "HERE" << endl;
		}

		// cout << cur_budget << endl;

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

		// cout << cur_budget << endl;
		// cout << X[i] << " " << len(cur_behind) << " " << len(cur_ahead) << endl;
		// cout << ahead.size() << endl;

		while(!ahead.empty() && !cur_behind.empty() && ahead.front() - ll(X[i]) <= ll(X[i]) - cur_behind.front())
		{
			cur_budget += ll(X[i]) + ll(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()-ll(X[i]) <= cur_budget)
			{
				cur_budget -= ahead.front()-ll(X[i]);
				cur_ahead.push_back(ahead.front());
				ahead.pop_front();
			} // yikes a lot of while loops
		}

		// cout << cur_budget << endl;

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

		// cout << X[i] << " " << len(cur_behind) << " " << len(cur_ahead) << endl;
		// cout << cur_budget << 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: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 32 / 32