### Maksim1744's blog

By Maksim1744, 3 years ago,

Continuing with the theme of absent editorials for old rounds, here is an editorial for Codeforces Round 171 (Div. 2). Even though there is an official editorial, it is only in russian and doesn't have solution for the last problem.

A

Editorial
Code

B

Editorial
Code

C

Editorial
Code

D

Editorial
Code

E

Editorial
Code
• +111

| Write comment?
 » 3 years ago, # |   0 In problem C could you elaborate the last part of editorial
•  » » 3 years ago, # ^ |   +8 Let's look at $tol[i]$. If $a[i - 1] < a[i]$, then $tol[i] = i$, otherwise $a[i - 1] \geqslant a[i]$ and we can continue longest nonincreasing sequence which ends in $a[i - 1]$ by adding $a[i]$, so $tol[i] = tol[i - 1]$.
 » 12 months ago, # |   0 How do we do B using Binary search?
•  » » 12 months ago, # ^ |   0 You create an array with the sum of prefixes from $1$ to $n$. Since the value of $a_i$ is always greater than $0$, the array of the sum of prefixes is always increasing.Given that, for each position $i$ you can ask with binary search what is the maximum $j$ that the sum of the interval [i, j] is less than t.Here I have my code that solves it with that logic: https://mirror.codeforces.com/contest/279/submission/208379855
•  » » » 12 months ago, # ^ |   0 Got it! Thanks so much, you're a godsend
 » 11 months ago, # |   0 Can we solve B with out Binary Search???
 » 9 months ago, # |   0 this problem give me time limit in test 9 but the time in worst case is 1e10 + 1e5 why it give my that please any one help me
 » 9 months ago, # |   0 l mean problem b
•  » » 7 months ago, # ^ |   0 share your submission
•  » » » 7 months ago, # ^ |   0 thanks proo i solved it
•  » » » » 7 months ago, # ^ |   0 ok bud
 » 9 months ago, # |   0 How C could be solved by Dynamic Programming?
 » 3 months ago, # |   0 hey i have a doubt ... int n,t; cin >> n >> t; vector vec(n); vector v(n+1,0); for(int i = 0 ;i> vec[i]; for(int i = 1; ivec[j-1]) { i++; }else { j--; } } } if(flag == 0) cout << 0 << endl;why is the above code not working for question B can anyone help !!