Submission #229567

#	Time	Username	Problem	Language	Result	Execution time	Memory
229567		monus1042	Rice Hub (IOI11_ricehub)	C++17	17 / 100	20 ms	1664 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define ll long long

int besthub(int R, int L, int X[], long long B)	{
	int ans=1;
	ll cost=0;

	int l=0,r=0;
	for (int i=1; i<R; i++){
		if (cost + (ll)(X[i] - X[0]) <= B){
			ans++;
			cost += (ll)(X[i] - X[0]);
			r++;
		}else break;
	}
	int forward[R], backward[R];
	for (int i=0; i<R; i++){
		int curr=X[i];
		int j, cnt=1;
		for (j=i; j<R && X[j] == curr; j++){
			forward[j]=cnt;
			cnt++;
		}
		j--;
		for (int k=j, c=1; k>=i; k--, c++){
			backward[k]=c;
		}
		i=j;
	}

	for (int i=1; i<R; i++){
		ll dist=X[i] - X[i-1];
		if (r<i){
			r=i;
		}else{
			cost -= dist * (ll)(r-(i-1));
		}
		cost += dist * (ll)(i-l - forward[i-1] + 1) * forward[i-1];
		if (cost == B) {}
		else if (cost < B){
			while(1){
				if (r+1 < R && cost + (ll)(X[r+1] - X[i]) <= B){
					cost += (ll)(X[r+1] - X[i]);
					r++;
				}else break;
			}
		}else{ // cost > B
			while(1){
				if (cost <= B) break;
				cost -= (ll)(X[i] - X[l]);
				l++;
			}
			//try to expand
			while(1){
				if (r+1 < R && cost + (ll)(X[r+1] - X[i]) <= B){
					cost += (ll)(X[r+1] - X[i]);
					r++;
				}else break;
			}
		}
		ans=max(ans, r-l+1);
	}

	return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:18:18: warning: variable 'backward' set but not used [-Wunused-but-set-variable]
  int forward[R], backward[R];
                  ^~~~~~~~

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