ashu_3916's blog

[help] G-Old Floppy Drive #702 (div 3)
By ashu_3916, history, 4 years ago, In English

can any one help me in finding wrong test case

i cant figure out from codeforces wrong submission report

problem link :1490-G my submission :check here

thanks in advance UPD : got the mistake, array should have been long long type , instead of int type

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem with your logic is how u are storing prefix. The prefix array wont be monotonically increasing. Consider the array $$$2, -3, -5, 10$$$. The prefix array would be $$$2, -1, -6, 4$$$. So you can't simply use lower_bound as it won't give correct position. So to solve this problem only store prefixes (with corresponding positions) that are in increasing order, i.e $$$2, 4$$$. In this you can use lower_bound and get the correct result.

My implementation

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hi , i think my prefix array is non decreasing as it stores max of previous max_sum or current sum.Though I think array name made it a bit confusing as it doesn't stores prefixes at all .

    ps : thanks for your code

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ashu_3916 (previous revision, new revision, compare).

→ Reply