Official
F - Potion Editorial by en_translator
We brute force through how many materials to mix.
Due to the constraint of \(\sum A_i \leq X\), when the number of materials \(C\) to mix is fixed, it is sufficient to solve the problem “what is the maximum of sum of exactly \(C\) elements chosen from \(A_i\), such that the sum is equal to \(X\) under \(\bmod C\)?”
This can be calculated in a total of \(O(NC^2)\) time with such DP that
\(dp[i][j][k]=\) the maximum of sum of \(j\) elements chosen from the first \(i\) materials, such that the sum is equal to \(k\) \(\bmod C\),
so the answer can be calculated in a total of \(O(N^4)\) time.
posted:
last update: