Long bus trip

Subtask 1

Try all

$2^M$ subsets of passengers that we want to keep in the bus. Once this is fixed, the problem becomes greedy.

Subtask 2/3

First, we need to realize that the problem is about whether to kick off each passenger or not.
Consider two adjacent water stations. The only way we can kick off passengers is by removing those closest to the second one, in order. (By getting too little water, a suffix of people will get off).

This still isn't enough for a polynomial solution. The key is the chauffeur- we must always give him water, otherwise we lose. This means that we are even more restricted in removing passengers. For every water station, we may remove passengers between it and the next time the chauffeur needs to drink.

This means that we can basically view the whole problem mod

$T$, because at every time that is

$0$ mod

$T$, the bus driver must drink.

Another important insight is that if we want to kick off someone, we will kick them off as early as possible. What we can do is compute for each person

$min[i]=$ the earliest water station that is directly after person i (in the sense that there is no other person between i and the water station mod

$T$) (

$min[i]$ will hold non-modded earliest, since we want to use it to compute the cost after we kick someone off). Another small detail is that we have to pretend that there is a water station at time

$X$ (since we can kick off people before the ending).
After having computed

$min[i]$, we can formulate our DP. We will process people in increasing order of

$D_j$. We will define

$dp[i]=$min cost if we consider people

$[0,i]$. We will compute each state by looking at earlier states (where we could've come from). Suppose we want to compute

$dp[i]$. There are two transitions:

• Do not kick off person i. Pay the price for them to stay for the whole ride, plus
  $dp[i-1]$.
• If
  $min[i]$ is defined (there is a water station directly after i): for some
  $j<i$, kick off all people in
  $[i,j]$. Then, all of these jumped off at time
  $min[i]$. It might be the case that it's better to start a kick-off-interval at an earlier fountain, but the DP will also explore that option. Don't forget to pay for the price of them jumping off, and also pay
  $dp[j-1]$.

Here is an implementation that gets 70 points. It is technically cubic, but SIMD takes care of it. It is trivial to make it

$O(N^2)$ with a prefix sum.

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

typedef long long ll;
#define int ll
const int inf = int(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define all(x) begin(x),end(x)

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

signed main()
{
	fast();

	int x, n, m, w, t;
	cin >> x >> n >> m >> w >> t;

	vi s(n);
	rep(i, n) cin >> s[i];
	s.push_back(x);

	vector<p2> people(m);
	rep(i, m) cin >> people[i].first >> people[i].second;
	sort(all(people));
	vi d(m);
	rep(i, m) d[i] = people[i].first;

	vi mint(m, inf);
	rep(i, n+1)
	{
		auto it = upper_bound(all(d), s[i]%t);
		if (it == begin(d)) continue;
		int ind = prev(it) - begin(d);
		mint[ind] = min(mint[ind], s[i]);
	}

	vi dp(m+1, inf);
	dp[0] = (x/t+1)*w;

	repp(i, 1, m + 1)
	{
		// never kick off person i
		dp[i] = dp[i - 1] + ((x - d[i - 1]) / t+1) * w;

		// start a kick off interval ending at i
		if (mint[i-1] == inf) continue;

		repp(j, 1, i+1)
		{
			int c = 0;
			repp(k, j, i + 1) c += people[k-1].second;
			dp[i] = min(dp[i], dp[j-1]+c+(i-j+1)*w*(mint[i-1]/t));
		}
	}

	cout << dp.back();

	return 0;
}

Subtask 4

The only slow part in the described solution is the transition of type 2, since we try every

$j<i$ for

$O(N^2)$ in total. We can realize that the function we are trying to minimize in transition 2 is a linear function, which lets us use convex hull trick to optimize it to

$O(N\log (N))$.