Submission #1666429


Source Code Expand

Copy
import java.io.*;
import java.util.*;

public class Main {
    private FastScanner in;
    private PrintWriter out;

    int solve(ArrayList<Integer> a) {
        int[][] dp = new int[2][a.size() + 1];
        for (int i = a.size() - 2; i >= 0; i--) {
            for (int j = 0; j < 2; j++) {
                int curSize = a.get(i) - j;
                dp[j][i] = Math.max((curSize == 0 ? dp[0][i + 1] : dp[0][i + 2]) + a.get(i + 1) * (curSize == 0 ? 0 : 1), dp[1][i + 1] + curSize);
            }
        }
        return Math.max(dp[0][0], dp[1][0]);
    }

    private void solve() {
        int n = in.nextInt();
        char[] a = in.next().toCharArray();
        int res = 0;
        for (int i = 0; i < n; ) {
            if (a[i] == '0') {
                i++;
                continue;
            }
            ArrayList<Integer> sizes = new ArrayList<>();
            int j = i;
            while (true) {
                while (j != n && a[j] == '1') {
                    j++;
                }
                sizes.add(j - i);
                i = j + 1;
                if (j == n || j + 1 == n || a[j + 1] == '0') {
                    break;
                }
                j++;
            }
            res += solve(sizes);
        }
        out.println(res);
    }

    private void run() {
        try {
            in = new FastScanner(new File("Main.in"));
            out = new PrintWriter(new File("Main.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    private void runIO() {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    private class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Main().runIO();
    }
}

Submission Info

Submission Time
Task D - 101 to 010
User qwerty787788
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 3509 Byte
Status
Exec Time 174 ms
Memory 41860 KB

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 125 ms 25808 KB
001.txt 113 ms 26452 KB
002.txt 137 ms 27316 KB
003.txt 117 ms 24788 KB
004.txt 124 ms 29748 KB
005.txt 140 ms 24460 KB
006.txt 99 ms 23508 KB
007.txt 109 ms 25300 KB
008.txt 82 ms 18388 KB
009.txt 125 ms 26800 KB
010.txt 130 ms 27716 KB
011.txt 154 ms 31668 KB
012.txt 162 ms 35460 KB
013.txt 169 ms 41860 KB
014.txt 170 ms 38024 KB
015.txt 165 ms 35704 KB
016.txt 163 ms 33372 KB
017.txt 169 ms 31140 KB
018.txt 151 ms 29744 KB
019.txt 136 ms 27732 KB
020.txt 128 ms 27880 KB
021.txt 130 ms 24516 KB
022.txt 129 ms 24164 KB
023.txt 130 ms 27240 KB
024.txt 131 ms 26080 KB
025.txt 131 ms 25312 KB
026.txt 131 ms 26856 KB
027.txt 131 ms 27716 KB
028.txt 121 ms 26720 KB
029.txt 174 ms 27996 KB
030.txt 139 ms 26436 KB
031.txt 125 ms 26084 KB
032.txt 129 ms 24932 KB
033.txt 136 ms 25408 KB
034.txt 140 ms 27588 KB
035.txt 143 ms 26724 KB
036.txt 126 ms 25668 KB
example0.txt 69 ms 18644 KB
example1.txt 68 ms 15700 KB