1999/2000 ms
- 02:57:15 Unsuccessful hacking attempt
- 03:13:10 Unsuccessful hacking attempt
- 03:13:18 Unsuccessful hacking attempt
- 03:13:53 Unsuccessful hacking attempt
- 03:13:59 Unsuccessful hacking attempt
- 03:14:16 Unsuccessful hacking attempt
- 03:17:38 Unsuccessful hacking attempt
- 03:19:16 Unsuccessful hacking attempt
- 03:19:30 Unsuccessful hacking attempt
- 03:20:19 Unsuccessful hacking attempt
- 03:20:21 Unsuccessful hacking attempt
- 03:20:49 Unsuccessful hacking attempt
- 03:21:31 Unsuccessful hacking attempt
- 03:21:54 Unsuccessful hacking attempt
- 03:22:12 Unsuccessful hacking attempt
- 03:22:33 Unsuccessful hacking attempt
- 03:23:01 Unsuccessful hacking attempt
- 03:23:19 Unsuccessful hacking attempt
- 03:23:56 Unsuccessful hacking attempt
- 03:24:45 Unsuccessful hacking attempt
- 03:32:37 Unsuccessful hacking attempt
- 03:43:11 Unsuccessful hacking attempt
- 03:44:49 Unsuccessful hacking attempt
- 03:45:17 Unsuccessful hacking attempt
- 03:49:26 Unsuccessful hacking attempt
- 03:52:07 Unsuccessful hacking attempt
- 03:54:15 Unsuccessful hacking attempt
- 03:54:44 Unsuccessful hacking attempt
- 04:07:35 Unsuccessful hacking attempt
- 04:09:54 Unsuccessful hacking attempt
- 04:10:08 Unsuccessful hacking attempt
- 04:20:09 Unsuccessful hacking attempt
- 04:37:57 Unsuccessful hacking attempt
- 04:39:22 Unsuccessful hacking attempt
- 04:45:43 Unsuccessful hacking attempt
- 04:49:15 Unsuccessful hacking attempt
- 04:52:11 Unsuccessful hacking attempt
- 05:09:40 Unsuccessful hacking attempt
- 05:56:25 Unsuccessful hacking attempt
- 05:57:03 Unsuccessful hacking attempt
- 06:55:06 Unsuccessful hacking attempt
- 08:05:42 Unsuccessful hacking attempt
- 09:35:15 Unsuccessful hacking attempt
- 10:12:43 Unsuccessful hacking attempt
- 10:18:41 Unsuccessful hacking attempt
- 10:22:24 Unsuccessful hacking attempt
- 10:23:44 Unsuccessful hacking attempt
- 10:31:17 Unsuccessful hacking attempt
- 10:36:35 Unsuccessful hacking attempt
- 11:35:52 Unsuccessful hacking attempt
- 11:37:09 Unsuccessful hacking attempt
- 11:37:34 Unsuccessful hacking attempt
- 11:46:50 Unsuccessful hacking attempt
- 11:46:56 Unsuccessful hacking attempt
- 11:50:31 Unsuccessful hacking attempt
- 11:52:25 Unsuccessful hacking attempt
- 12:03:54 Unsuccessful hacking attempt
- 12:04:32 Unsuccessful hacking attempt
- 12:10:46 Unsuccessful hacking attempt
- 12:12:56 Unsuccessful hacking attempt
- 12:13:54 Unsuccessful hacking attempt
- 12:36:01 Unsuccessful hacking attempt
- 12:37:40 Unsuccessful hacking attempt
- 12:43:01 Unsuccessful hacking attempt
- 12:45:35 Unsuccessful hacking attempt
- 12:49:09 Unsuccessful hacking attempt
- 12:50:55 Unsuccessful hacking attempt
- 13:06:04 Unsuccessful hacking attempt
- 13:09:44 Unsuccessful hacking attempt
- 13:11:34 Unsuccessful hacking attempt
- 13:12:07 Unsuccessful hacking attempt
- 13:12:48 Unsuccessful hacking attempt
- 13:13:34 Unsuccessful hacking attempt
- 13:27:01 Unsuccessful hacking attempt
- 13:28:41 Unsuccessful hacking attempt
- 13:31:04 Unsuccessful hacking attempt
- 13:32:33 Unsuccessful hacking attempt
- 13:34:26 Unsuccessful hacking attempt
- 13:34:57 Unsuccessful hacking attempt
- 13:35:46 Unsuccessful hacking attempt
- 13:36:05 Unsuccessful hacking attempt
- 13:36:19 Unsuccessful hacking attempt
- 13:36:27 Unsuccessful hacking attempt
Blessed by the $$$O(n^2 \log n)$$$ no-brainer! Try harder hacking next time :P
What is your approach that takes exactly $$$1999/2000$$$ ms?
I brute force the last painted element. That part is $$$O(n)$$$. Then, I get the subarrays from the left and from the right of it and sort them. The idea is that if I get at least one element on the left of our pivot and one from the right, I can guarantee that it is a valid last painted element. So, for $$$k\geq2$$$ I take the maximum on the left and on the right of our last painted element. Then, I sort all the other $$$n-3$$$ elements (without the last painted and the two maximums) and take the $$$k-2$$$ biggest ones. Sorting the remaining $$$n-3$$$ elements take $$$O(n \log n)$$$, so the overall complexity is $$$O(n^2 \log n)$$$. For $$$k = 1$$$, we just do a linear solution brute forcing the first painted item, noticing that the last one can only by the first or the last element of the array.
Here is the code!
Same approach
Were you worried?
Yes. During the contest it took 1984ms on pretests. I was considering implementing the $$$O(n)$$$ solution after getting D, but after 12 WAs I was a bit tilted and didn't have the patience to re-implement B.
Yeah, i too implemented in O(n*k*2) tc , it worked fine , Due to constraints I did that. I got it in 343ms. So didn't optimised it.
funniest post lol
mine N*N*logN got TLE on test 4. So optimised it to N*N.
Same lol 311066463 but i guess no one dared to challenge my wisdom :D
311053932 1999ms gang
limao
lmao