| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1331601 | matrix081 | 쌀 창고 (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;
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=1;i<=L;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];
}
int main(){
int arr[7] = {1,2,10,12,14,25,30};
return besthub(7, 50, arr, 6);
}