| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1333426 | hayford08 | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include "ricehub.h"
#include <iostream>
// #include <map>
#include <vector>
#include <algorithm>
using namespace std;
int besthub(int R, int L, int X[], long long B) // this is my ricehub implementation for now
//will come back later to try and improve it;
{
// return R;
// kind of like the binary search on answer, check which place when the hub is placed will
// give us a total transport cost <=B(baht)
// so here taking the answer on which I am binary searching to be the position to place the hub
// so starting from the middle then I compute the total cost to place it those places
// total cost is the absolute value of the distance between a hub and our rice hub
// long long lb = 0;
// long long rb = L;
// long long mid = lb + (rb-lb)/2;
// learnt about sliding windows and checking to see how I can add it
long long sum_of_dist_to_hub = 0;
long long median;
long long left = 0;
long long max_truckloads = 0;
for(long long right = 0; right<R;right++){
sum_of_dist_to_hub = 0;
long long median_index = (left+right)/2;
for(long long i=left;i<=right;i++){
sum_of_dist_to_hub+= abs(X[i] - X[median_index]);
}
while (sum_of_dist_to_hub>B && left<R){
sum_of_dist_to_hub = 0;
left++;
long long median_index = (left+right)/2;
for(long long i=left;i<=right;i++){
sum_of_dist_to_hub+= abs(X[i] - X[median_index]);
}
}
max_truckloads = max(max_truckloads, (right-left+1)); // cause it is 0 indexed [1,2,4] will be left =0 right = 2 2-0 = 2 but there are actually 3 items so +1;
}
// cout<< max_truckloads << endl;
return max_truckloads;
}
int main(){
int arr[7] = {1,2,10,12,14};
return besthub(5, 20, arr, 2);
}
// int besthub(int R, int L, int X[], long long B) // this is my ricehub implementation for now
// //will come back later to try and improve it;
// {
// // return R;
// // kind of like the binary search on answer, check which place when the hub is placed will
// // give us a total transport cost <=B(baht)
// // so here taking the answer on which I am binary searching to be the position to place the hub
// // so starting from the middle then I compute the total cost to place it those places
// // total cost is the absolute value of the distance between a hub and our rice hub
// // long long lb = 0;
// // long long rb = L;
// // long long mid = lb + (rb-lb)/2;
// long long hub_size = (long long)(X.size() -1);
// long long median_index = hub_size/2;
// long long abs_dist_sums = 0;
// for(long long i = 0;i<R;i++){
// abs_dist_sums += abs(X[i] - X[median_index]);
// }
// }
// int number_of_rice_hubs;
// vector<int> rice_hub_num_arr;
// // map <long long, bool> precomputed_dist_cost_to_ricehub;
// while(true){ // total TC : O(L^2);
// long long sum_of_dist_to_opt_hub = 0;
// for(int i=X[0];i<=R;i++){ // i here is where I am placing the hub;
// number_of_rice_hubs = 0;
// sum_of_dist_to_opt_hub = 0;
// for(int j=1;j<=L;j++){
// if(sum_of_dist_to_opt_hub + abs(X[j] - i)>B){
// continue;
// }
// if(X[j]){
// if((sum_of_dist_to_opt_hub + abs(X[j] - i))<=B){
// sum_of_dist_to_opt_hub += abs(X[j] - i);
// number_of_rice_hubs++;
// }
// }
// }
// rice_hub_num_arr.push_back(number_of_rice_hubs);
// }
// break;
// }
// sort(rice_hub_num_arr.begin(), rice_hub_num_arr.end());
// int size = rice_hub_num_arr.size();
// // cout<< rice_hub_num_arr[size-1];
// return rice_hub_num_arr[size-1];