I still can't figure out how to solve this problem after I read the tuturial. Can you write your idea carefully :(

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3520 |

2 | tourist | 3461 |

3 | Um_nik | 3367 |

4 | apiadu | 3351 |

5 | mnbvmar | 3332 |

6 | Benq | 3330 |

7 | LHiC | 3276 |

8 | TLE | 3271 |

9 | Radewoosh | 3251 |

10 | ecnerwala | 3241 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 189 |

2 | Errichto | 188 |

3 | tourist | 180 |

4 | Radewoosh | 173 |

5 | vovuh | 166 |

6 | pikmike | 165 |

7 | ko_osaga | 162 |

8 | Um_nik | 160 |

9 | rng_58 | 155 |

10 | farmersrice | 152 |

I still can't figure out how to solve this problem after I read the tuturial. Can you write your idea carefully :(

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/25/2020 06:47:51 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

you want to solve the problem for ( 1 , n ) where 1 is first array and n is the last array. for solving ( i, n) first solve ( i+1 , n ), thus you'll have a integer S, ( 0<= S <= a[i+1] ) and if S>= a[i] then s= s-a[i] , and if s<a[i] then s = a[i] — s. and you can easily use an array to save the sign of any numbers from 1 to n.

I got AC using your idea.:) I really appreciate you and care about your country.:)

I think your expression is better than the tuturial.:)

thank U, but where's the tuturial?

Let solve this task for all suffixes of array in increasing of size order. For last element it's easy, because it's in [0..

a_{n}]. letf_{i}is the sum we get fora_{i}..a_{n}Let's add 1 element. Then

a_{i}—f_{i + 1}is in [-a_{i}..a_{i}], soa_{i}—f_{i + 1}orf_{i + 1}—a_{i}is OK.You always help me a lot!;)