Educational Codeforces Round 28 A. Curriculum Vitae（读懂题意后的暴力水题）

心已赠人 2022-06-09 12:51 117阅读 0赞

A. Curriculum Vitae

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

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.

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.

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.

Input

The first line contains one integer number *n* (1 ≤ *n* ≤ 100).

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.

Output

Print one integer — the maximum number of games Hideo can leave in his CV so that no unsuccessful game comes after a successful one.

Examples

input

4
    1 1 0 1

output

input

6
    0 1 0 0 1 0

output

input

1
    0

output

题解：

昨天因为看国足然后就没打比赛（赢了hhhhhh，武磊牛逼），然后今天上午做这题的时候卡了一会。。主要是题意很难懂

题意：

王大锤有一堆作品，1表示成功，0表示失败，让你从一堆作品里面剔除几个，使得成功作的后面不能有失败作

坑点：

可以把1的作品也剔除掉。。。因为数据很小直接暴力解决了

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-7
    #define lson k*2
    #define rson k*2+1
    int a[105];
    int main()
    {
        int i,j,n,ans,temp;
        scanf("%d",&n);
        ans=1;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<n;i++)
        {
            temp=0;
            for(j=0;j<=i;j++)
            {
                if(!a[j])
                    temp++;
            }
            for(j=i;j<n;j++)
            {
                if(a[j])
                    temp++;
            }
            ans=max(ans,temp);
        }
        printf("%d\n",ans);
        return 0;
    }