Show all threads Hide all threads Show all messages Hide all messages |

O(n) | 0blivium | 1296. Hyperjump | 16 Sep 2019 02:37 | 2 |

O(n) **0blivium** 4 Jan 2019 02:58 Note, the required algorithm is known as the Kadane's algorithm and runs in O(n). |

В чем прикол? | AdiZer0 | 1296. Hyperjump | 18 Mar 2019 18:40 | 2 |

Я написал рекурсию которая каждый раз делила отрезок на два и брала максимальный среди ответа всех таких отрезков которых поделила.(типо Merge Sort). У меня был memory limit на 3 тесте. Это значить рекурсия берет память? Да, берёт. Рекурсия хранит итерации в стеке. |

Why WA4? | Tigra | 1296. Hyperjump | 7 Nov 2018 20:19 | 2 |

#include <bits/stdc++.h> using namespace std; const int maxn = 60007; int a[maxn]; int dp[maxn]; int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; dp[0] = 0; for (int i = 1; i <= n; ++i) dp[i] = max(dp[i - 1] + a[i], max(0,a[i])); int ans = *max_element(dp, dp + n); cout << ans; system("pause"); return 0; } Re: Why WA4? **Khujamurod Murtozakulov (Tashkent U of IT)** 7 Nov 2018 20:19 max(0, a[i]). This is wrong! You must get sum of consecutive elements.
*Edited by author 07.11.2018 20:19* |

HAHA easy solved in 5 minutes and AC | IlushaMax | 1296. Hyperjump | 6 Jun 2017 19:27 | 4 |

I had TLE 10. My algoritm: i just for all possible sequence found sum and check if this sum is Max. And I have no idea how solve this problem another way. Can you (or somebody, please) help with algo? Идейку подайте пожалуйста) |

Why WA#1? | rkhapov | 1296. Hyperjump | 26 Jul 2016 15:30 | 2 |

My program outputs 187, but i got WA#1. Why? "My program outputs 187, but i got WA#1. Why?" it means that the first test is not like that has been given in the example |

help! WA9 | Egor Stepanov [mikroz] | 1296. Hyperjump | 3 Dec 2015 10:01 | 3 |

help! WA9 **Egor Stepanov [mikroz]** 28 Oct 2008 03:52 I can't understand why. Can anybody help me? Try these two tests: 5 10 -5 3 -1 15 ---- 5 15 -1 3 -5 10 In both right answer is 22. |

Please ! Need help..my algoritm is wright, but ! WA9 | gippotalamus | 1296. Hyperjump | 3 Dec 2015 09:58 | 3 |

> > i found my mistake
*Edited by author 20.11.2005 00:44* I have wa#9 but I can't found mistake :( what is test 9? |

example 2 | Vladislav | 1296. Hyperjump | 9 Jan 2015 22:37 | 1 |

Why in example 2, such a response? 3 -1 -5 -6 answer 3? |

why my sollution take WA on test #3 | Pavel Sergeev | 1296. Hyperjump | 27 Dec 2013 07:02 | 2 |

var p:int64; i,n,x:integer; max:int64; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); readln(n); readln(p); max:=p; for i:=1 to n-1 do begin readln(x); if x>=p+x then p:=x else p:=p+x; if p>max then max:=p; end; if max<0 then writeln(0) else writeln(max); end.
*Edited by author 18.11.2009 00:20*
*Edited by author 18.11.2009 00:21*
*Edited by author 18.11.2009 00:23* |

WA #4 | Shree | 1296. Hyperjump | 19 Dec 2013 13:49 | 3 |

WA #4 **Shree** 23 Jan 2013 17:49 Hi guys, any ideas on test #4? getting WA there один из элементов и есть максимальное значение 3 -5 90 -20 работает и при таком вводе |

Why 187 in first sample?? | Ilia [SamSU] | 1296. Hyperjump | 4 Jun 2013 20:56 | 2 |

the maximum is 31-41+59+26-53+58+97=177 or am I wrong on the way to the right idea? please help oh oh, I'm sorry for silly question. I understood why is there such answer |

To everyone : Algorithm to solve this problem ! Very easy ! | Phan Hoài Nam - Đại học Ngoại ngữ Tin Học TP.HCM | 1296. Hyperjump | 18 Jan 2012 20:58 | 4 |

calculate : fmax(n) = max(fmax(n-1)+value(n),value(n)); Why? Consider p1 = 5, p2 = -2 fmax(1) = 5 fmax(2) = max( 5+(-2), -2 ) = 3 But if i = j = 1 fmax(2) = 5 Or I got wrong understanding of the task? F[i] is max values of sequence with the final element is a[i]. Finally, answer will be max( F[1], ... F[n] ). Sorry because of English. It's wrong algorithm and more hard than right. |

How do better? (my solution 0.031 208kb) | Ont | 1296. Hyperjump | 3 Aug 2011 16:44 | 4 |

Best solution - 0.015. How to improve? I do not use array. Only 5 vars - (3 integer and 2 longint) I use inc([longint], number) instead of [longint]:= [longint] + number;
*Edited by author 07.02.2008 18:14* my solution is also 0.031 and I used same "vars" as you and no array. my algo if O(N). and what is most interesting, one time the result was 0.015! after it i send same solution. it was 0.031 again.
*Edited by author 07.02.2008 18:15* I have 4 int vars, O(N) algo. I solved it 5 times already, and still (0.031,108). Useless. |

Secod demonstration test | D_T_F | 1296. Hyperjump | 3 Aug 2011 15:57 | 2 |

No more question. I read the text badly.
*Edited by author 23.03.2009 03:56* I got it too. Sorry for this post ^^ For anyone who can't understand this example: remember that the first number means the size of a sequence given, not the first its element!
*Edited by author 03.08.2011 16:16* |

Why WA6? | {USU} Averin Artyom | 1296. Hyperjump | 16 Jul 2011 21:54 | 2 |

Why WA6? **{USU} Averin Artyom** 19 Sep 2010 10:13 Here's the code... #include<iostream>; using namespace std; int main(){ int k=0; int max=0; int maxi=0; int n=0; cin >> n; for (int i=1;i<=n;i++) { cin >> k; if (max+k < 0) max = 0; if (max+k > 0) max = max + k; if (max > maxi) maxi = max; } cout << maxi; return 0; } cin >> k; max+=k; if (max < 0) max = 0; if (max > maxi) maxi = max; |

C# - AC | Varun Sharma | 1296. Hyperjump | 5 May 2009 11:26 | 1 |

C# - AC **Varun Sharma** 5 May 2009 11:26 Hi, Well, the only thing to keep in mind for this problem is that final answer cannot be negative. If it comes to negative then output 0. Secondly, just start adding the numbers from the beginning and keep track of the maximum sum. For example, if you add first three terms and sum comes to 500 and then the fourth term is -500, then don't loose the previous 500 sum. Keep it somewhere, but make your new sum 0. Then start adding from 5th term (0 + 5th term + ....). Whenever you add just check whether the new one is greater than 500 or not ? If it is then replace it with that. Varun
*Edited by author 05.05.2009 11:30*
*Edited by author 05.05.2009 11:31* |

Why WA? I can't understand! | Dr.Dro | 1296. Hyperjump | 18 Jul 2008 03:16 | 2 |

Here is my code: program Project2; {$APPTYPE CONSOLE} uses SysUtils; var n,max,i,sum,a:integer; begin max:=0; sum:=0; readln(n); for i:=1 to n do begin readln(a); sum:=sum+a; if sum>max then max:=sum; end; writeln(max); end. I've tested it. It is allright. But i get WA!!! Why? because you're trying to make set from i = 0 to all of j. But answer may differ. |

Problem 1296: I got AC in 0.046 sec. | Edward Bolshakov [NNTU] | 1296. Hyperjump | 18 Jul 2008 03:13 | 2 |

The problem is easy, IMHO. I don't understand why so few people have solved it. |

YES!!! I got AC!!! | I am get tester... | 1296. Hyperjump | 7 Feb 2008 18:06 | 5 |

time 0.046 memory 906 КБ (wow!!!) O(N) = (N * log N) It isn't cool, 'cause the normal (and simple) solution is O(N),not O(N * log N). I got AC 0.015 165 kb O(N)
*Edited by author 13.08.2005 20:17* AC 0.015, 104 kb Memory :) |

A faster solution | Darth Niculus(Ivan Nicolae) | 1296. Hyperjump | 17 Apr 2007 22:09 | 3 |

Is there a faster solution that the one with 3 for's. I would apreciate if there is one. Yes, using dynamic programming (i use this method and stuck at WA 7) |