Submission #1673613
Source Code Expand
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ int N; string S; int dp[501010]; //--------------------------------------------------------------------------------------------------- int nxt[501010], bak[501010]; void _main() { cin >> N >> S; S += "#"; int bk = -1; rep(i, 0, N) { bak[i] = bk; if (S[i] == '0') bk = i; } int nx = N; rrep(i, N - 1, 0) { nxt[i] = nx; if (S[i] == '0') nx = i; } rep(i, 0, N) { dp[i + 1] = max(dp[i + 1], dp[i]); // 1011111... if (S[i] == '1') { if (1 <= bak[i] && S[bak[i] - 1] == '1') { int c = i - bak[i]; dp[i + 1] = max(dp[i + 1], dp[bak[i] - 1] + c); } } if (S[i] == '1') { // ...1111101 if (nxt[i] < N - 1 && S[nxt[i] + 1] == '1') { int c = nxt[i] - i; dp[nxt[i] + 2] = max(dp[nxt[i] + 2], dp[i] + c); } } } //rep(i, 0, N + 1) printf("dp[%d] = %d\n", i, dp[i]); cout << dp[N] << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 101 to 010 |
User | hamayanhamayan |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 2028 Byte |
Status | AC |
Exec Time | 11 ms |
Memory | 6812 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0.txt, example1.txt |
All | 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 | AC | 5 ms | 4500 KB |
001.txt | AC | 4 ms | 3536 KB |
002.txt | AC | 5 ms | 4372 KB |
003.txt | AC | 4 ms | 3536 KB |
004.txt | AC | 5 ms | 3920 KB |
005.txt | AC | 6 ms | 4500 KB |
006.txt | AC | 3 ms | 2816 KB |
007.txt | AC | 4 ms | 3408 KB |
008.txt | AC | 2 ms | 2432 KB |
009.txt | AC | 8 ms | 5652 KB |
010.txt | AC | 8 ms | 6812 KB |
011.txt | AC | 8 ms | 6684 KB |
012.txt | AC | 9 ms | 6684 KB |
013.txt | AC | 9 ms | 6812 KB |
014.txt | AC | 10 ms | 6684 KB |
015.txt | AC | 11 ms | 6812 KB |
016.txt | AC | 10 ms | 6684 KB |
017.txt | AC | 10 ms | 6812 KB |
018.txt | AC | 10 ms | 6684 KB |
019.txt | AC | 10 ms | 6812 KB |
020.txt | AC | 8 ms | 6812 KB |
021.txt | AC | 9 ms | 6812 KB |
022.txt | AC | 9 ms | 6684 KB |
023.txt | AC | 10 ms | 6684 KB |
024.txt | AC | 10 ms | 6684 KB |
025.txt | AC | 10 ms | 6684 KB |
026.txt | AC | 10 ms | 6684 KB |
027.txt | AC | 10 ms | 6684 KB |
028.txt | AC | 10 ms | 6684 KB |
029.txt | AC | 10 ms | 6684 KB |
030.txt | AC | 10 ms | 6684 KB |
031.txt | AC | 10 ms | 6812 KB |
032.txt | AC | 10 ms | 6812 KB |
033.txt | AC | 10 ms | 6812 KB |
034.txt | AC | 10 ms | 6684 KB |
035.txt | AC | 10 ms | 6684 KB |
036.txt | AC | 10 ms | 6684 KB |
example0.txt | AC | 2 ms | 2304 KB |
example1.txt | AC | 2 ms | 2304 KB |