[USACOJan2020S]BerryPicking

Bessie and her little sister Elsie are picking berries in Farmer John's berry patch. Farmer John's patch has exactly N berry trees (1≤N≤1000); tree i contains exactly B_i berries (1≤B_i≤1000). Bessie has exactly K baskets (1≤K≤1000, K even). Each basket can hold as many berries from a single tree as Bessie wants, but cannot contain berries from two different trees as their flavors will clash with each other. Baskets may remain empty.
Bessie wants to maximize the number of berries she collects. However, Farmer John wants Bessie to share with her little sister, and so Bessie will have to give Elsie the ${\frac{K}{2}}$ baskets with the largest number of berries. This means that Elsie may even end up with more berries than Bessie, which is very unfair, but unfortunately, sibling dynamics are not always fair.

Help Bessie figure out the maximum number of berries she can collect.

then she receives two baskets each with 4 berries, giving her 8 berries in total.

#include<bits/stdc++.h> using namespace std; const int maxN = 1000 + 10; int a[maxN], n, k, d[maxN]; int main(){ cin >> n >> k; k >>= 1; for(int i = 1; i <= n; i++) cin >> a[i]; int ans = 0; for(int i = 1; i <= 1000; i++){ for(int j = 1; j <= i; j++) d[j] = 0; for(int j = 1; j <= n; j++) d[i] += a[j] / i, d[a[j] % i]++; if(d[i] < k) continue; d[i] -= k; int sum = 0, x = k; for(int j = i; x && j; j--) if(x > d[j]) sum += d[j] * j, x -= d[j]; else sum += x * j, x = 0; ans = max(ans, sum); } cout << ans; return 0; }

详情