/**
* Another problem from tinjyu's training, though we didn't directly go through the
* full solution. The "minimum sum of dist. to a point" is classic; we know that
* point b is the median, i.e. any val in [(n/2)-th_num, #(n/2+1)-th_num]. The obs.
* here is that the actual val we take is irrelevant. Since n is even, the val would
* be cancelled out so the
* prize = #sum_of_the_(n/2)_larger_num - #sum_of_the_(n/2)_smaller_num.
*
* This means in each round, we maximize #sum_of_(n/2)_num - #sum_of_remaining
* because this naturally finds the larger n numbers to minus the n smaller ones
* In k=1, we know that if we wanna find a num to be part of the smaller numbers,
* this num has to be the smallest in its row. Similarly, the largest num in the row
* shall be picked if it's a "larger" element. With some greedy arguments, the n rows
* with a larger #min + #max shall pick its maximum, while the remaining rows/colors
* should pick its minimum.
*
* Sadly, this greedy approach isn't correct for other values of k, but the thing we
* know (and can prove) using our experience with k=1 is:
* Each time a "plus" element is picked, it must be largest value of that
* color. Each time when a "minus" element is picked, it must be the
* smallest value in the row.
* Yep, this is valid, though we don't know what colors should be picked as "plus" or
* "minus" (yet).
*
* I then looked at [S3], which i didn't finish. After this, I went to [S4], i.e.
* k=n. In this scenario, every num in x[][] is either added to or subtracted from
* the final ans. Naturally, we want the largest nm/2 values to be "plus", while the
* nm/2 smallest ones to be "minus". It turns out that we can always give a
* construction that achieves this. Imagine that we've decided which elements are
* "plus" & which ones are "minus"; as long as the num of rows with all "plus" <= n/2
* and num of rows with all "minus" <= n/2, we can always find a round of tickets
* with n/2 "plus" & n/2 "minus". If the contrary happens, either "plus" or "minus"
* elements have a num >nm/2, which is impossible. This means we can always induct
* downwards.
*
* Wow, [S4] is really inspiring. Now, for each row of values a prefix is chosen for
* "minus" and a suffix is chosen for "plus". We can use dp to find exactly nk/2
* "minus" and exactly nk/2 "plus" with maximum profit, and give a construction since
* this is just [S4] with m -> k. Well, at least I thought so, but this results in a
* O((nm)^2) dp (assuming k is close to m). This implies that we can only score 12
* pts in [S5], AND we'll have to code tons more code to score previous subtasks.
* (I admit that this is sth I hate about IOI)
* Define r[i][j] to be the difference in color i when we pick j "plus". In other
* words, r[i][j] = #sum_of_suffix_with_len_j - #sum_of_prefix_with_len_(k-j). It's
* easy to see that r[i][] is increasing, but after carefully examining this, the
* difference between adjacent terms in r[i][] is decreasing. Therefore, we can just
* greedily find the nk/2 "plus". Finally, I've finished this problem!
*
* Time Complexity: O(mn * log(mn))
* Implementation 1 (Full solution, greedy + sorting + construction)
*/
#include <bits/stdc++.h>
#include "tickets.h"
typedef long long ll;
typedef std::vector<int> vec;
struct pair_t {
ll diff;
int color;
int plus; // num of plus
};
ll find_maximum(int k, std::vector<vec> x) {
int n = x.size(), m = x[0].size();
std::vector<pair_t> pairs;
ll price = 0;
for (int i = 0; i < n; i++) {
std::vector<ll> prefix(m + 1);
prefix[0] = 0;
for (int j = 0; j < m; j++)
prefix[j + 1] = prefix[j] + x[i][j];
std::vector<ll> r(k + 1);
for (int j = 0; j <= k; j++)
r[j] = -prefix[k - j] + (prefix[m] - prefix[m - j]);
price += r[0];
for (int j = 1; j <= k; j++) {
assert(r[j] >= r[j - 1]);
pairs.push_back(pair_t{r[j] - r[j - 1], i, j});
}
for (int j = 1; j < k; j++)
assert(r[j] - r[j - 1] >= r[j + 1] - r[j]);
}
std::sort(pairs.begin(), pairs.end(),
[](const pair_t& p1, const pair_t& p2) {
return p1.diff > p2.diff || (p1.diff == p2.diff && p1.plus < p2.plus);
});
vec plus(n, 0);
for (int l = 0; l < n * k / 2; l++)
price += pairs[l].diff, plus[pairs[l].color] = pairs[l].plus;
vec minus(n);
for (int i = 0; i < n; i++) {
minus[i] = k - plus[i];
assert(plus[i] >= 0 && minus[i] >= 0);
}
vec left(n, 0), right(n, m - 1);
std::vector<vec> tickets(n, vec(m, -1));
for (int r = 0; r < k; r++) {
int m_count = 0, p_count = 0;
std::vector<bool> must(n, false); // if i must be minus or must be plus
for (int i = 0; i < n; i++) {
if (plus[i] == 0) {
tickets[i][left[i]] = r, left[i]++;
minus[i]--, m_count++, must[i] = true;
} else if (minus[i] == 0) {
tickets[i][right[i]] = r, right[i]--;
plus[i]--, p_count++, must[i] = true;
}
}
for (int i = 0; i < n; i++) {
if (!must[i]) {
if (m_count < n / 2)
tickets[i][left[i]] = r, left[i]++, m_count++, minus[i]--;
else if (p_count < n / 2)
tickets[i][right[i]] = r, right[i]--, p_count++, plus[i]--;
else
std::abort(); // absurd
}
}
}
allocate_tickets(tickets);
return price;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
21 ms |
2308 KB |
Output is correct |
6 |
Correct |
463 ms |
51320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
21 ms |
2892 KB |
Output is correct |
6 |
Correct |
489 ms |
63156 KB |
Output is correct |
7 |
Correct |
518 ms |
69024 KB |
Output is correct |
8 |
Correct |
4 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
296 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
6 ms |
976 KB |
Output is correct |
13 |
Correct |
20 ms |
2676 KB |
Output is correct |
14 |
Correct |
17 ms |
2772 KB |
Output is correct |
15 |
Correct |
557 ms |
73828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
27 ms |
3476 KB |
Output is correct |
6 |
Correct |
5 ms |
824 KB |
Output is correct |
7 |
Correct |
5 ms |
980 KB |
Output is correct |
8 |
Correct |
713 ms |
83752 KB |
Output is correct |
9 |
Correct |
685 ms |
82528 KB |
Output is correct |
10 |
Correct |
655 ms |
82628 KB |
Output is correct |
11 |
Correct |
704 ms |
83716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
508 KB |
Output is correct |
13 |
Correct |
24 ms |
2284 KB |
Output is correct |
14 |
Correct |
19 ms |
2376 KB |
Output is correct |
15 |
Correct |
23 ms |
2764 KB |
Output is correct |
16 |
Correct |
29 ms |
3528 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
2 ms |
340 KB |
Output is correct |
20 |
Correct |
33 ms |
2980 KB |
Output is correct |
21 |
Correct |
23 ms |
3756 KB |
Output is correct |
22 |
Correct |
25 ms |
3652 KB |
Output is correct |
23 |
Correct |
27 ms |
4160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
21 ms |
2308 KB |
Output is correct |
12 |
Correct |
463 ms |
51320 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
21 ms |
2892 KB |
Output is correct |
18 |
Correct |
489 ms |
63156 KB |
Output is correct |
19 |
Correct |
518 ms |
69024 KB |
Output is correct |
20 |
Correct |
4 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
296 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
6 ms |
976 KB |
Output is correct |
25 |
Correct |
20 ms |
2676 KB |
Output is correct |
26 |
Correct |
17 ms |
2772 KB |
Output is correct |
27 |
Correct |
557 ms |
73828 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
2 ms |
492 KB |
Output is correct |
32 |
Correct |
27 ms |
3476 KB |
Output is correct |
33 |
Correct |
5 ms |
824 KB |
Output is correct |
34 |
Correct |
5 ms |
980 KB |
Output is correct |
35 |
Correct |
713 ms |
83752 KB |
Output is correct |
36 |
Correct |
685 ms |
82528 KB |
Output is correct |
37 |
Correct |
655 ms |
82628 KB |
Output is correct |
38 |
Correct |
704 ms |
83716 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
2 ms |
340 KB |
Output is correct |
41 |
Correct |
2 ms |
340 KB |
Output is correct |
42 |
Correct |
2 ms |
468 KB |
Output is correct |
43 |
Correct |
2 ms |
468 KB |
Output is correct |
44 |
Correct |
2 ms |
468 KB |
Output is correct |
45 |
Correct |
1 ms |
212 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
2 ms |
468 KB |
Output is correct |
48 |
Correct |
2 ms |
468 KB |
Output is correct |
49 |
Correct |
2 ms |
468 KB |
Output is correct |
50 |
Correct |
2 ms |
508 KB |
Output is correct |
51 |
Correct |
24 ms |
2284 KB |
Output is correct |
52 |
Correct |
19 ms |
2376 KB |
Output is correct |
53 |
Correct |
23 ms |
2764 KB |
Output is correct |
54 |
Correct |
29 ms |
3528 KB |
Output is correct |
55 |
Correct |
1 ms |
340 KB |
Output is correct |
56 |
Correct |
2 ms |
468 KB |
Output is correct |
57 |
Correct |
2 ms |
340 KB |
Output is correct |
58 |
Correct |
33 ms |
2980 KB |
Output is correct |
59 |
Correct |
23 ms |
3756 KB |
Output is correct |
60 |
Correct |
25 ms |
3652 KB |
Output is correct |
61 |
Correct |
27 ms |
4160 KB |
Output is correct |
62 |
Correct |
56 ms |
6960 KB |
Output is correct |
63 |
Correct |
55 ms |
7048 KB |
Output is correct |
64 |
Correct |
77 ms |
10184 KB |
Output is correct |
65 |
Correct |
254 ms |
28860 KB |
Output is correct |
66 |
Correct |
322 ms |
36748 KB |
Output is correct |
67 |
Correct |
6 ms |
1108 KB |
Output is correct |
68 |
Correct |
5 ms |
956 KB |
Output is correct |
69 |
Correct |
488 ms |
52588 KB |
Output is correct |
70 |
Correct |
586 ms |
63408 KB |
Output is correct |
71 |
Correct |
709 ms |
84984 KB |
Output is correct |
72 |
Correct |
619 ms |
84140 KB |
Output is correct |
73 |
Correct |
679 ms |
78616 KB |
Output is correct |
74 |
Correct |
532 ms |
62864 KB |
Output is correct |
75 |
Correct |
584 ms |
65104 KB |
Output is correct |