NOI.sg - 2019 - Feast

C++

Like a normal Aliens Trick problem, we're going to binary search on the maximum $\lambda$ where the number of subarrays used is $\geq k$.

Now, for a given $\lambda$, we're going to calculate the number of people in an optimal food arrangement such that we subtract $\lambda$ for every person.

Let's have $\texttt{dp}[i][j:\{0,1\}]$ represent the maximum sum of satisfaction of an arrangement of the first $i$ plates, given that $j=0/1$ implies whether plate $i$ is being used. Let $\texttt{cnt}[i][j]$ represent the number of people used in an optimal arrangement of $\texttt{dp}[i][j]$.

For our $\texttt{dp}$ transitions, we have

and

because we either begin a new subarray or we continue an existing subarray.

Since calculating $\texttt{dp}$ takes $\mathcal O(N)$ time, and we're binary searching on the range $[0, \sum a[i]]$, the time complexity is $\mathcal{O}(N\log{\sum a[i]})$.

Copy
#include <bits/stdc++.h>
using namespace std;

const int N = 300000;
const long long INF = (long long)300000 * 1000000000;
const long double EPS = 1e-3;

int n, k, a[N + 1];
pair<long double, int> dp[N + 1][2];