Submission #1666114


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(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 3477 Byte
Status
Exec Time 169 ms
Memory 40440 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 121 ms 25168 KB
001.txt 108 ms 25556 KB
002.txt 134 ms 27220 KB
003.txt 109 ms 25044 KB
004.txt 131 ms 29396 KB
005.txt 133 ms 27180 KB
006.txt 95 ms 21204 KB
007.txt 100 ms 21716 KB
008.txt 82 ms 19028 KB
009.txt 122 ms 24916 KB
010.txt 130 ms 27788 KB
011.txt 153 ms 31444 KB
012.txt 160 ms 34216 KB
013.txt 169 ms 40440 KB
014.txt 168 ms 40324 KB
015.txt 164 ms 37204 KB
016.txt 162 ms 34032 KB
017.txt 156 ms 31936 KB
018.txt 147 ms 26800 KB
019.txt 143 ms 29016 KB
020.txt 132 ms 25692 KB
021.txt 121 ms 24292 KB
022.txt 130 ms 27716 KB
023.txt 131 ms 24292 KB
024.txt 131 ms 26948 KB
025.txt 130 ms 26852 KB
026.txt 126 ms 25168 KB
027.txt 123 ms 29268 KB
028.txt 121 ms 27620 KB
029.txt 128 ms 27616 KB
030.txt 132 ms 26472 KB
031.txt 141 ms 26128 KB
032.txt 126 ms 24292 KB
033.txt 135 ms 25640 KB
034.txt 136 ms 25828 KB
035.txt 144 ms 27808 KB
036.txt 142 ms 24000 KB
example0.txt 68 ms 19156 KB
example1.txt 68 ms 19156 KB