Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Since the value of K is fixed, we can just check through to see what happens if
- we try to fill the K baskets with a certain number of berries, and optimize for
- the least K / 2 baskets. Since the maximum number of berries on a single tree is at most 10^3, it is enough to loop through from 1 to the tree with the highest number of berries...
- Case 1 --> In the best case scenario, we will have all K baskets be filled the same quantity in which case, update out answer relative to the current iteration.
- Case 2 --> In the case where we have at least >= K / 2, find the number of baskets that can take the number of berries we are currently checkiing for, then for the remaining baskets, it is enough to sort the array based on the greatest remainder and fill the basket with those. We also update our answer relative to the current iteration.
- Case 3 --> If the number of fillable baskets is less < K / 2, no point, because we most likely cannot arrive at an optimal answer. So we skip
- */
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define int ll
- #define endl "\n"
- int MOD;
- bool cmp(int &a, int &b){
- return a % MOD > b % MOD;
- }
- int32_t main(){
- freopen("berries.in", "r", stdin);
- freopen("berries.out", "w", stdout);
- int N, K;
- cin>>N>>K;
- vector<int>Array(N);
- int max_berries = 0;
- for(int i = 0; i < N; i++){
- cin>>Array[i];
- max_berries = max(max_berries, Array[i]);
- }
- int answer = 0;
- for(int i = 1; i <= max_berries; i++){
- int baskets = 0;
- for(int j = 0; j < N; j++){
- baskets += (Array[j] / i);
- }
- //Case 1
- if(baskets >= K){
- answer = max(answer, ((K / 2) * i));
- continue;
- }
- // Case 2
- if(baskets >= K / 2){
- int val = ((baskets - (K / 2)) * i);
- MOD = i;
- sort(Array.begin(), Array.end(), cmp);
- // int to = K - baskets;
- for(int j = 0; j < N and j + baskets < K; j++){
- val += Array[j] % MOD;
- }
- answer = max(answer, val);
- }
- }
- cout<<answer;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
