codeforces-scrape

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

846A.md (1741B)


      1 Source: https://codeforces.com/problemset/problem/846/A
      2 
      3 A. Curriculum Vitae
      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 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Hideo Kojima has just quit his job at Konami. Now he is going to find a new place to work. Despite being such a well-known person, he still needs a CV to apply for a job.
     22 
     23 During all his career Hideo has produced *n* games. Some of them were successful, some were not. Hideo wants to remove several of them (possibly zero) from his CV to make a better impression on employers. As a result there should be no unsuccessful game which comes right after successful one in his CV.
     24 
     25 More formally, you are given an array *s*1, *s*2, ..., *s**n* of zeros and ones. Zero corresponds to an unsuccessful game, one — to a successful one. Games are given in order they were produced, and Hideo can't swap these values. He should remove some elements from this array in such a way that no zero comes right after one.
     26 
     27 Besides that, Hideo still wants to mention as much games in his CV as possible. Help this genius of a man determine the maximum number of games he can leave in his CV.
     28 
     29 Input
     30 
     31 The first line contains one integer number *n* (1 ≤ *n* ≤ 100).
     32 
     33 The second line contains *n* space-separated integer numbers *s*1, *s*2, ..., *s**n* (0 ≤ *s**i* ≤ 1). 0 corresponds to an unsuccessful game, 1 — to a successful one.
     34 
     35 Output
     36 
     37 Print one integer — the maximum number of games Hideo can leave in his CV so that no unsuccessful game comes after a successful one.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 4  
     45 1 1 0 1
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 3
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 6  
     58 0 1 0 0 1 0
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 4
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 1  
     71 0
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 1
     78 ```