Розбір

Problem Author:	Illia Fursov
Prepared by:	Illia Fursov, Illia Shevchenko
Editorial by:	Illia Fursov

Group 1: $a_{i} = 0$ for all $i$ $(1 \leq i \leq n)$ .

If someone moves forward — then someone needs to move back.

Taking this fact into account, we cannot move any of the customers at all, and the only valid order of people in a queue is the initial one, and the answer is just $t_{1} + (t_{1} + t_{2}) + (t_{1} + t_{2} + t_{3}) + \dots + (t_{1} + t_{2} + \dots + t_{n})$ .

To show that this sum can be calculated in $O (n)$ time complexity, let's open the parentheses and see that: $t_{1}$ is used in every sum, $t_{2}$ is used in every sum, except for the first one, ..., $t_{i}$ is used in $n - i + 1$ sums. That means that the answer can be written down as: $t_{1} \times n + t_{2} \times (n - 1) + ... + t_{n - 1} \times 2 + t_{n} \times 1$ .

Time and memory complexity: $O (n)$

Group 2: $n \leq 10$ .

In this group, $n$ is small enough to allow checking all the possible orders / permutations of people, checking all the $a_{i}$ conditions for them and taking the minimum possible sum out of them all.

Time complexity: $O (n! \cdot n)$

Memory complexity: $O (n)$

Group 3: $n \leq 20$ .

In this group, checking all the permutations will not already pass, but there is still another solution — dynamic programming over bitmasks.

We can consider $d p [ma s k]$ as a minimum result for the $ma s k$ of places, taken by the first $p o p co u n t (ma s k)$ (the number of $1$ -bits in $ma s k$ ) customers, and updates in this case are "setting the $p o p co u n t (ma s k) + 1$ 'th customer on the place which is not taken yet if the $a [p o p co u n t (ma s k) + 1]$ -condition is satisfied". The answer for the problem is $d p [2^{n} - 1]$ (i.e. the minimum possible result when all the places are taken).

Time complexity: $O (n \cdot 2^{n})$

Memory complexity: $O (2^{n})$

Group 4: $a_{i} = n - i$ for all $i$ $(1 \leq i \leq n)$ .

This group is, technically, the opposite for the first one. In that group we could not move any of the customers, and in this group we can move any customer at any position. It holds because $i + a_{i} = i + n - i = n$ , which means that every customer is fine even with moving to the very back of the queue.

So, now we have a total freedom of how to reorder the customers. To find out the most optimal order, let's look at the formula we got solving the first group: $t_{1} \times n + t_{2} \times (n - 1) + ... + t_{n - 1} \times 2 + t_{n} \times 1$ . Here, the answer can be calculated the same way, but the order of $t_{i}$ 's near $n, n - 1, \dots, 1$ coefficients can be any other.

The most optimal order of $t_{i}$ 's here is actually their increasing order.

The answer can be calculated by sorting the array $t$ and using the formula, mentioned in the beginning.

Time complexity: $O (n l o g n)$ (because of sorting)

Memory complexity: $O (n)$

Groups 5, 6 and 7 require different implementations to be solved, but use the same idea.

And the idea is: to get the best result, we need to reorder the customers in decreasing order of their $t_{i}$ 's, taking for each the largest position that is still possible to take (the largest such position $j$ that it is not yet taken and $i + a_{i} \leq j$ )

To prove this idea, let's prove three facts:

All the $a_{i}$ -conditions will be satisfied;
The generated order is complete and valid (all the customers will take each position from $1$ to $n$ );
Out of all the possible orders, there are no better orders than the generated one.

Group 5: $n \leq 4000$ .

In this group, placing of each person can be done by iterating through all the positions from $i + a_{i}$ to $1$ and taking the maximum free one. In this case, placing each person takes $O (n)$ time and there are $n$ people in total. Thus:

Time complexity: $O (n l o g n + n^{2}) = O (n^{2})$

Memory complexity: $O (n)$

Group 6: $t_{i} \leq 100$ .

In this group, all the people can be grouped by their $t_{i}$ 's and reordered using the same algorithm as in the previous group (if there are some people with the same $t_{i}$ 's, then is does not matter who will be placed earlier).

Time complexity: $O (n \cdot ma x_t)$

Memory complexity: $O (n)$

Group 7: no additional constraints.

In this group, we can use a set to store free positions, and take the maximum available one, which is not greater than $i + a_{i}$ using set.lower_bound() / set.upper_bound() function (positions can be stored in form of their negative values if it's more convenient). Then placing each of $n$ customers will take $O (l o g n)$ time, which results in acceptable $O (n l o g n)$ time complexity.

Full implementation (C++):

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N = 1e5 + 12;
 
int n;
int a[N], t[N];
int p[N];
int q[N];
 
bool cmp(int i, int j) {
	return t[i] > t[j];
}
 
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> t[i];
	for (int i = 0; i < n; i++)
		cin >> a[i];
 
	iota(p, p + n, 0);
	sort(p, p + n, cmp);
 
	set <int> unused;
	for (int i = 0; i < n; i++)
		unused.insert(-i);
	for (int pi = 0; pi < n; pi++) {
		int i = p[pi];
		int c = min(n - 1, i + a[i]);
		auto now = unused.lower_bound(-c);
		assert(now != unused.end()); // making sure that there is at least one available position
		int pos = -(*now);
		unused.erase(now);
		q[pos] = i;
	}
 
	ll ans = 0, sum = 0;
	for (int i = 0; i < n; i++) {
		assert(i <= q[i] + a[q[i]]); // making sure that all a[i] conditions are satisfied
		sum += t[q[i]];
		ans += sum;
	}
	cout << ans << endl;
}

Time complexity: $O (n l o g n)$

Memory complexity: $O (n)$