Is greedy right?

Revision en1, by shinchankosen, 2024-07-01 19:08:42

Problem D in EPIC Institute of Technology Round Summer 2024

I'm not good at English, and this is my first post. I usually post here in Japanese. Nice to meet you.

These are my solution.

$$$O(N^2)$$$

Tutorial says DP, and most Accepted programs are DP, too.

But, my program is greedy. Is greedy the correct way to solve it?

C++ 92 ms

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

use Lazy Segment Tree. If the above greedy is correct, then lazysegtree can be used.

C++ 62 ms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English shinchankosen 2024-07-01 19:17:02 9
en1 English shinchankosen 2024-07-01 19:08:42 712 Initial revision (published)