codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

327A.md (1583B)


      1 Source: https://codeforces.com/problemset/problem/327/A
      2 
      3 A. Flipping Game
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Iahub got bored, so he invented a game to be played on paper.
     22 
     23 He writes *n* integers *a*1, *a*2, ..., *a**n*. Each of those integers can be either 0 or 1. He's allowed to do exactly one move: he chooses two indices *i* and *j* (1 ≤ *i* ≤ *j* ≤ *n*) and flips all values *a**k* for which their positions are in range [*i*, *j*] (that is *i* ≤ *k* ≤ *j*). Flip the value of *x* means to apply operation *x* = 1 - *x*.
     24 
     25 The goal of the game is that after exactly one move to obtain the maximum number of ones. Write a program to solve the little game of Iahub.
     26 
     27 Input
     28 
     29 The first line of the input contains an integer *n* (1 ≤ *n* ≤ 100). In the second line of the input there are *n* integers: *a*1, *a*2, ..., *a**n*. It is guaranteed that each of those *n* values is either 0 or 1.
     30 
     31 Output
     32 
     33 Print an integer — the maximal number of 1s that can be obtained after exactly one move.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 5  
     41 1 0 0 1 0
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 4
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 4  
     54 1 0 0 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 4
     61 ```
     62 
     63 Note
     64 
     65 In the first case, flip the segment from 2 to 5 (*i* = 2, *j* = 5). That flip changes the sequence, it becomes: [1 1 1 0 1]. So, it contains four ones. There is no way to make the whole sequence equal to [1 1 1 1 1].
     66 
     67 In the second case, flipping only the second and the third element (*i* = 2, *j* = 3) will turn all numbers into 1.