I'm not a racist, but just because of your color :D

So , people don't like dynamic scoring??
Every new thing is hated in the beginning :p

add me, i am blocked

Why only experts??? O_O

Iam sure you are the winner :P

yes

Sadly Codeforces system seems not working properly as my submission gives wrong ans before starting evaluation :(

Disagree -1 XD
It's so clear to me. But I can't solve problems. I'm a noob :(

It's dynamic programming. DP[current second][last speed]. But I spent a lot of time on understanding the statement.

V increasing while we can decrease V to Vlast

print(sum(min(v1 + d * i, v2 + d * (t - i - 1)) for i in range(t)))
increase our speed as fast as we can. Also with decreasing
(can't code without brackets highlighting :( and forget we need sum it, not print :( )

This problem can be solved without using dynammic programming .. just traverse first from left to right and then right to left maintain minimum of both side at each second . sum them up :)

if v1 + (t-1)*d <= v2, we know the best way is to increase the velocity by d every second. Otherwise, the speed would first increase to a top speed, let's say Vmax, then decrease to v2. We can enumerate the top speed Vmax to find the answer.

maintain 2 arrays of size t.

first has first element as v1 and contain maximum speed that can be attained at any time by increasing previous element by d.

second have last element as v2 and contain maximum speed that can is possible at any time by increasing later element by d.

example- if v1=10 and v2=30, t=5 and d=4

array1- 10 14 18 22 26 array2- 14 18 22 26 30

add elements from array1 to answer untill array1[i]<=array2[i], then add elements from array2.

int main(){ int v1,v2; cin >> v1 >> v2; int t,d; cin >> t; cin >> d; int ans=0;

while(t--){
    ans+=v1;
    v1=min(v1+d,v2+((t-1)*d));
}
cout << ans << endl;
return 0;

}

i did it without dp.... simply take a array 'A' of size t; A[1]=v1; A[t]=v2;

for<- 2 to t-1 A[i]+=d;

and traverse from back and check if abs(A[i]-A[i+1]>d) make abs exactly d...by changing A[i];

then add all A[i];

You can solve it by 2 pointers..

Bipartite matching !!

My kind of brute-force algorithm couldn't pass pretest 9 but I think the idea is correct.

Store the people in an array of vector, where vector v[i] stores people shaking hands with i people, initialise current index of all vector to 0.

Now start from 0, if current index of v[0] is less than v[0].size(), it means there is a person that can enter now.add this person to solution vector, increment 0 to 1 and repeat.

If, current index becomes >= v[i].size(), then check for current index that are possible, eg. for i=7, other states possible are 7-3=4, 4-3=1 and so on.If you cant find any valid state that has current index < v[i].size(), break out of loop.

Edit: The idea is correct.It passed the system test after removing a stupid bug.

We only need to simulate the whole thing. But, we postpone groupings as late as possible.

Let's say there is X ungrouped people and next one comes. First check if there is exists (remain) a person who shake hands with X people. If yes, allow him to shake hands with X people and add 1 to current no of ungrouped people.

If not, form a group and try again, no of hand shakes becomes X = X - 3. Repeat if necessary. If ultimately not possible because there is not enough people to form groups anymore, output Impossible.

D solution:

Simple greedy: take the largest numbers first, e.g. 0 1 2 3 4 5 6 7, 5 6, 2 3 4, 0 1 2.

I solved with greedy :D

200000 stack

Your A must be define as a long long... I have hacked 9 people like you :)

You have declared sum as int, but if I give you 200000 times 1000000 as d? Then the power goes to 11. Thanks. :)

Ответ: нет.

P.S. Не стоит жадничать на константы от которых не сильно изменяется время работы программы, но при этом может упасть решение.

X + Y — Y would always result in X even if overflow occurs.

As you can see in case 50 the answers are equal to the input.

10685565
я думал ну совсем все знают что делать...

В решении с ТЛ ты удаляешь из начала вектора. erase() работает за O(N).

Это же решение только будем удалять из конца вектора, а не из начала.

У меня в решении по E достаточно было изменить 3 на 4 и WA68 превратилось в AC.

UPD: Хотя то что решение заходит при 4 — это из-за слабых тестов. Моё решение бы упало при N = 200000, M < N / 2, и более менее нормальных остальных значениях.

Вокруг есть добрые люди, которые могут объяснить задачу по лучше всякого разбора, если их вежливо об этом попросить.

you used std::lower_bound, which has linear complexity
use set::lower_bound and you get AC: 10685831

use s.lower_bound(x) instead of lower_bound(s.begin(), s.end(), x)

This have been discussed many many many times in Codeforces

I have a TLE on system tests, but I used 3 smaller multimaps(each element only in one multimap, depending on shakes[i]%3 and I cycled between them) and used insert, lower_bound ( s.lower_bound) , erase, empty operations. What could go wrong? Isn`t is supposed to be N*log N solution? Or is it not good enough? http://mirror.codeforces.com/contest/534/submission/10675989

When calculating DP you are setting your initial ret value to be 0. However, your recursive call can return you negative infinity, because there is no solution. Since you update ret to be a max of a previous ret value i+get(...), you lose that information. So for a state that doesn't lead anywhere, you will return 0, which is wrong. As a result, when the correct solution is 1+2+3+4+5+6+5+3+2+1, your program can do 1+2+3+4+5+6+7+8+9+0 (10 can't reach 1, so we use 0).

Change line 50 from ret=0LL; to ret=-inf; and you'll get an AC :)

Good luck!