제출 #248829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
248829		eohomegrownapps	쌀 창고 (IOI11_ricehub)	C++14	100 / 100	327 ms	3452 KiB

ricehub

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

//return number of rice fields
vector<ll> s;
vector<ll> coord;

ll totalcostrtol(int hub, int e){//e hub
	assert(e>=hub);
	return s[e]-s[hub]-((e-hub)*coord[hub]);
}

ll totalcostltor(int hub, int e){//hub e
	assert(e<=hub);
	return coord[hub]*(hub-e+1)-(s[hub]-(e==0?0:s[e-1]));
}
int n;
ll success(int ind, ll range, ll b){
	//returns max truckloads of rice, or -1 if not possible
	//using all rice up to and including coord (plus a bit more if necessary)
	//cout<<"check "<<ind<<" "<<range<<": ";
	ll total = 0;
	ll ricehubs = 0;
	int left = lower_bound(coord.begin(), coord.end(), coord[ind]-range)-coord.begin();
	//cout<<left<<" ";
	total+=totalcostltor(ind,left);	
	int right = upper_bound(coord.begin(), coord.end(), coord[ind]+range)-coord.begin()-1;
	//cout<<right<<'\n';
	total+=totalcostrtol(ind,right);
	//cout<<total<<'\n';
	if (total>b){
		//cout<<"fail"<<'\n';
		return -1;
	}
	ricehubs+=right-left+1;
	if (left-1>=0){
		int left2 = lower_bound(coord.begin(), coord.end(), coord[left-1])-coord.begin();
		ll numadd = (min(b-total,ll((left-left2)*(coord[ind]-coord[left-1])))/(coord[ind]-coord[left-1]));
		ricehubs+=numadd;
		total+=numadd*(coord[ind]-coord[left-1]);
	}
	if (right+1<n){
		int right2 = upper_bound(coord.begin(), coord.end(), coord[right+1])-coord.begin()-1;
		ricehubs+=(min(b-total,ll((right2-right)*(coord[right+1]-coord[ind])))/(coord[right+1]-coord[ind]));
	}
	
	return ricehubs;
}

int besthub(int R, int L, int X[], long long B){
	ll maxfields = 0;
	//coords from 1 to L
	n = R;
	coord = vector<ll>(X,X+n);
	s.resize(n);
	s[0]=coord[0];
	for (int i = 1; i<n; i++){
		s[i]=s[i-1]+coord[i];
	}
	for (int i = 0; i<n; i++){
		//cout<<"consider "<<i<<'\n';
		//consider rice field i
		ll numfields = 1;
		//go left
		ll l=0,r=max(coord[n-1]-coord[i],coord[i]-1)+10;
		while (l<=r){
			ll mid = (l+r)/2;
			if (success(i, mid, B)!=-1){
				l=mid+1;
			} else {
				r=mid-1;
			}
		}
		//l is leftmost hub possible
		ll sc = success(i,l-1,B);
		//cout<<sc<<'\n';
		maxfields=max(maxfields,sc);
	}
	return maxfields;
}

컴파일 시 표준 에러 (stderr) 메시지

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:65:6: warning: unused variable 'numfields' [-Wunused-variable]
   ll numfields = 1;
      ^~~~~~~~~

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