Due to technical reasons Codeforces may be unavailable on April 21st from 01:00-07:00 (MSK). ×

### urusant's blog

By urusant, history, 4 years ago, ,

Только что прошел очередной этап opencup-а. Предлагаю обсудить задачи здесь.

В частности, хотелось бы узнать решения H и J.

•
• +24
•

 » 4 years ago, # |   0 Can anybody share their solution of D, I and J?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 I: Firstly, if we will use songs with numbered songi1, songi2, ..., songik, then the total satisfaction will be maximized, if fi1 ≤ fi2 ≤ ... ≤ fik or fi1 ≥ fi2 ≥ ... ≥ fik. We wil sort of fi. Let's dp(i,j) — first i songs assigned and j total length of songs. dp(i, j) = max{dp(k, j - ti) + pi - (fi - fk)2} = max{dp(k, j - ti) - fk2 + 2fkfi} + pi - fi2 Then we can use convex hull trick optimization. Code
•  » » » 4 years ago, # ^ |   0 Thanks a lot for your solution.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +16 Hi! I'm writer of problem I! Thanks for your solving!
•  » » 4 years ago, # ^ |   +16 Hi, I'm the writer of the problem C and H. How was the problems?I posted the solution of the problem D here.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Hi, can you show me your code for problem H? I always get TL on test 25. My codeUPD I found your code
•  » » » » 4 years ago, # ^ |   +5 Some of testers use min-cost-flow, and I used Hungarian method. My solution takes 180ms in worst case.You can show my codes for all problems from here.
•  » » 4 years ago, # ^ |   0 I'm the writer of the problem J. I posted my brief editorial for this problem as a blog entry.