oj.uz

Submission #248827

# Submission time Handle Problem Language Result Execution time Memory
248827 2020-07-13T14:03:26 Z eohomegrownapps Rice Hub (IOI11_ricehub) C++14
0 / 100
 55 ms 768 KB 
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

//return number of rice fields
vector<ll> s;
vector<int> 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();
		ricehubs+=(min(b-total,ll((left-left2)*(coord[ind]-coord[left-1])))/(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<int>(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)+1;
		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;
}

Compilation message

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Incorrect 1 ms 256 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -