After reading this you should be able to solve the problem for N,L,R<=1e18

Being able to solve a problem and hating it are not mutually exclusive. I too dislike such problems and take slightly more time to solve them than my rating peers.

Lookup is not necessarily O(1) in unordered map. Read This

Damn it ninjas cutting onions in my room again :(

Personally, I loved the work you did with atcoder. Be it the short, crisp and on point algorithmic problems or the efficient user interface. You will be missed. You'll always inspire me :)

I think publishing the cheater's names and handles in a high viewed blog post or a separate "leaderboard" is the way to go. No better deterrence than public humiliation.

Can you predict mine senpai? Although I gotta warn you the volatility of this stock is high xD

This reminds me of another question I've been meaning to ask. Has anyone compared their performance under the influence of Ally/Mary? I used to think that Mary would enhance my performance but I actually lost 150 rating that day. Can anyone else share their experience?

s1mple>stewie2k>dev1ce

This is one of my favorite recursion problem.

Nvm I'm wrong

This greedy is not so hard to prove. Every time we encounter a 1 we necessarily have to chose a subarray including this element. Since we're certain that all elements before it are 0, it can be said that the most optimal solution includes the subarray starting with this 1 if we're allowed to ie: i+k<=n since it leaves the maximum 0s, otherwise choosing the last k elements if possible deletes all possible 1s that we might encounter whilst 'wasting' minimal 0s.

Yep greedy works

I changed <= to < here is the code but it's getting WA verdict. Whereas when I use this code I get an AC. I can't figure out what's wrong with using a custom made comparator versus the inbuilt one in set.

The reason why I'm so sure that my comparator has a problem is because I submitted the solution with a set of pair of shortest distance and node, and it works fine.

Thanks a lot I didn't know this at all. I'll remember this now onward. After I fixed that compare function to return false when elements are equal though the last subtask is accepted it shows WA on some other ones which was not the case before. I'm confused and pretty sure the problem is with my comp function but now what is it? Thanks in advance.

I implemented this version of dijikstra from this source only. I didn't use a priority queue cause I wanted to write a shorter code without all those pairs using a set which I'm more comfortable with. But I'm doing something wrong and I can't figure out what :(

I read it, made my own custom hash function and got an AC using unordered_map. Thanks a lot. This was a really informative blog post.

Auto comment: topic has been updated by manijuana (previous revision, new revision, compare).