Educational rounds are Unrated.

You are downvoting me badly implying the task is actually EASY. But see, even DIV1 coder did not solved it by his/her own, but just COPYPASTED solution http://codeforces.net/contest/808/submission/27140269

You can just overflow cup with maximum volume.

Test:
3 12
4 4 4

Lets pick K souvenirs with W=3, so we can take souvenirs with sumW <= m — k * 3 (if negative, skip this K). Lets store souvenirs with w=1,2 in one array sorted by decreasing value c / w. So, if we should choose some souvenirs from this array with sumW = x, we greedily takes souvenirs until sumW <= x (after that sumW == x or x — sumW == 1 — in this case we should take largest souvenir with w=1 or remove smallest souvenir with cost w=1 and take with w=2). So, if we iterates over K in decreasing order, we can maintain second value by two pointers technique.

Not sure if my solution is the best, but it worked: So left part is 0, right is whole sum. Go through the array subtracting from right and adding to left. Add current element to set. Check if left is equal to right — solution is YES. When left is greater than right, check if difference between them is even. If yes, check if difference / 2 is in the set. If yes — we have the solution. (I also made the same thing moving right to left, but I guess it may be unnecessary)

Lets store two multisets(left, right). sum(set) — sum of the all elements in set. Lets add [1, 1] to the left and [2, n] to the right. On the next step there a 2 main cases:
1. sum(left) = sum(right) -> YES
2. sum(left) > sum(right) (if opposite swap the sets). if left set containse value (sum(left) — sum(right)) / 2 -> YES

After this step we remove a[i + 1] from right set and add it to left set.

First of all, maintain for each element y the first and last appearance in the array. Now fix the position i where array will be split.

If sum(1, i) = sum(i + 1, n), we are done.

Else, if sum(1, i) > sum(i + 1, n) we need to remove a element x from (1, i) and add it to (i + 1, n). We will have that sum(1, i) — x = sum(i + 1, n) + x <=> sum(1, i) — sum(i + 1, n) = 2 * x, x = (sum(1, i) — sum(i + 1, n)) / 2. Also x must be integer, so sum(1, i) — sum(i + 1, n) must be divisible by 2. To check if x appears in (1, i), just check if first appearance of x is <= i.

If sum(i + 1, n) > sum(1, i) we use same idea, but now x = (sum(i + 1, n) — sum(1, i)) / 2 must appear in (i + 1, n).

Also check that after moving an element, both parts will be non-empty.

On top of the window with accepted solution source code there is link "hack it!".

answer for this testcase is NO and your code is giving right answer

It's most probably pow().

http://codeforces.net/blog/entry/21844

The following link will be useful to solve the problem : http://www.geeksforgeeks.org/window-sliding-technique/

Check case

5

1 1 4 1 1

Read statements + constraints again carefully. Also if you look at the editorials, you will see they are very different.

It was more like this one

you need to use a map or multiset

because when you insert some element in a set 5 times for example and then erasing it once

you are erasing it completely , not decreasing it's frequency

I haven't read the problems but surely most of the time, whether or not you use unordered_set/map is largely orthogonal to the main point of solving the actual problem. So if you choose to use a data structure which is known to have a bad worst case, you really have no one to blame but yourself (and yes, even normal CF rounds have anti-hashing cases).

But if for some reason you need the extra speed, you can just generate a random number and xor your usages of the unordered_set/map with it to prevent it from breaking on specific known cases.