Submission #1669794


Source Code Expand

Copy
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
char s[SIZE];
int dp[SIZE][4];
int an;
template <class T>
void maa(T& x,T y){
    if(x<y)x=y;
}
template <class T>
void mii(T& x,T y){
    if(x>y)x=y;
}
void solve(VI& d){
    REP(i,SZ(d))REP(j,4)dp[i][j]=-1;
    dp[0][0]=0;
    REP(i,SZ(d)-1){
        REP(j,4)maa(dp[i+1][0],dp[i][j]);
        if(dp[i][0]!=-1){
            if(d[i+1]==1){
                maa(dp[i+1][1],dp[i][0]+d[i]);
            }
            else{
                maa(dp[i+1][1],dp[i][0]+d[i+1]);
                maa(dp[i+1][2],dp[i][0]+d[i+1]-1);
                maa(dp[i+1][3],dp[i][0]+d[i]);
            }
        }
        if(dp[i][1]!=-1){
            maa(dp[i+1][0],dp[i][1]);
        }
        if(dp[i][2]!=-1){
            if(d[i+1]==1){
                maa(dp[i+1][1],dp[i][0]+1);
            }
            else{
                maa(dp[i+1][1],dp[i][0]+d[i+1]);
                maa(dp[i+1][2],dp[i][0]+d[i+1]-1);
            }
        }
        if(dp[i][3]!=-1){
            if(d[i+1]==1){
                maa(dp[i+1][1],dp[i][0]+d[i]-1);
            }
            else{
                maa(dp[i+1][1],dp[i][0]+d[i+1]);
                maa(dp[i+1][2],dp[i][0]+d[i+1]-1);
                maa(dp[i+1][3],dp[i][0]+d[i]-1);
            }
        }
    }
    int ma=0;
    REP(i,4){
        ma=max(ma,dp[SZ(d)-1][i]);
    }
    an+=ma;
}
int main(){
    DRI(N);
    RS(s);
    VPII pp;
    for(int i=0,j;i<N;i=j){
        if(s[i]=='0'){
            j=i+1;
        }
        else{
            for(j=i+1;j<N&&s[j]=='1';j++);
            pp.PB(MP(i,j));
        }
    }
    for(int i=0,j;i<SZ(pp);i=j){
        VI d;
        d.PB(pp[i].S-pp[i].F);
        for(j=i+1;j<SZ(pp)&&pp[j].F==pp[j-1].S+1;j++){
            d.PB(pp[j].S-pp[j].F);
        }
        solve(d);
    }
    printf("%d\n",an);
    return 0;
}

Submission Info

Submission Time
Task D - 101 to 010
User dreamoon
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2961 Byte
Status
Exec Time 12 ms
Memory 3448 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:11: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     DRI(N);
           ^
./Main.cpp:88:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     RS(s);
          ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt
All 0 / 700 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt 3 ms 2560 KB
001.txt 3 ms 2688 KB
002.txt 5 ms 2940 KB
003.txt 4 ms 2688 KB
004.txt 5 ms 2940 KB
005.txt 7 ms 2940 KB
006.txt 3 ms 2560 KB
007.txt 3 ms 2688 KB
008.txt 2 ms 2304 KB
009.txt 4 ms 2688 KB
010.txt 3 ms 2304 KB
011.txt 6 ms 2940 KB
012.txt 8 ms 3448 KB
013.txt 10 ms 3448 KB
014.txt 11 ms 3448 KB
015.txt 12 ms 3448 KB
016.txt 11 ms 3448 KB
017.txt 10 ms 3448 KB
018.txt 8 ms 3448 KB
019.txt 6 ms 2940 KB
020.txt 3 ms 2304 KB
021.txt 3 ms 2304 KB
022.txt 3 ms 2304 KB
023.txt 3 ms 2304 KB
024.txt 3 ms 2304 KB
025.txt 3 ms 2304 KB
026.txt 3 ms 2304 KB
027.txt 3 ms 2304 KB
028.txt 3 ms 2304 KB
029.txt 3 ms 2304 KB
030.txt 3 ms 2304 KB
031.txt 3 ms 2304 KB
032.txt 3 ms 2304 KB
033.txt 3 ms 2304 KB
034.txt 3 ms 2432 KB
035.txt 4 ms 2560 KB
036.txt 5 ms 2688 KB
example0.txt 2 ms 2304 KB
example1.txt 2 ms 2304 KB