Submission #1667149


Source Code Expand

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

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

    int size(int full, int type) {
        switch (type) {
            case 0:
                return 0;
            case 1:
                return 1;
            case 2:
                return full - 1;
            default:
                return full;
        }
    }

    int solve(ArrayList<Integer> a) {
        int[][] dp = new int[4][a.size() + 1];
        for (int i = a.size() - 2; i >= 0; i--) {
            for (int j = 0; j < 4; j++) {
                for (int nj = 0; nj < 4; nj++) {
                    int mySize = a.get(i) - size(a.get(i), j);
                    int nextSize = size(a.get(i + 1), nj);
                    int dpPrev = dp[nj][i + 1];
                    dp[j][i] = Math.max(dp[j][i], dpPrev);
                    if (mySize != 0 && nextSize != 0) {
                        dp[j][i] = Math.max(dp[j][i], dpPrev + Math.max(mySize, nextSize));
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i < 4; i++) {
            res = Math.max(res, dp[i][0]);
        }
        return res;
    }

    HashMap<String, Integer> ans = new HashMap<>();

    int stupid(String s) {
        Integer res = ans.get(s);
        if (res == null) {
            res = 0;
            for (int i = 0; i + 2 < s.length(); i++) {
                if (s.substring(i, i + 3).equals("101")) {
                    res = Math.max(res, 1 + stupid(s.substring(0, i) + "010" + s.substring(i + 3)));
                }
            }
            ans.put(s, res);
        }
        return res;
    }

    void solve() {
        int n = in.nextInt();
        out.println(solve(in.next()));
    }

    private void solve123() {
        Random rnd = new Random(123);
        final int MAX = 20;
        for (int it = 0; it < 123133; it++) {
            System.err.println("it = " + it);
            int n = 1 + rnd.nextInt(MAX);
            char[] a = new char[n];
            for (int i = 0; i < n; i++) {
                a[i] = (char) ('0' + rnd.nextInt(2));
            }
            String s = new String(a);
            int st = stupid(s);
            int my = solve(s);
            if (my != st) {
                System.err.println("s = " + s);
                System.err.println("my = " + my + ", correct = " + st);
                throw new AssertionError();
            }
        }
    }

    private int solve(String s) {
        int n = s.length();
        char[] a = s.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);
        }
        return 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 700
Code Size 5469 Byte
Status
Exec Time 234 ms
Memory 41336 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt
All 700 / 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 27476 KB
001.txt 119 ms 24940 KB
002.txt 146 ms 31872 KB
003.txt 135 ms 29316 KB
004.txt 140 ms 29436 KB
005.txt 160 ms 30248 KB
006.txt 109 ms 23768 KB
007.txt 138 ms 23996 KB
008.txt 78 ms 21716 KB
009.txt 159 ms 24912 KB
010.txt 129 ms 25668 KB
011.txt 173 ms 36236 KB
012.txt 180 ms 41336 KB
013.txt 185 ms 36612 KB
014.txt 191 ms 38136 KB
015.txt 199 ms 36984 KB
016.txt 181 ms 39424 KB
017.txt 194 ms 34000 KB
018.txt 234 ms 30452 KB
019.txt 190 ms 27984 KB
020.txt 122 ms 24532 KB
021.txt 125 ms 28540 KB
022.txt 129 ms 24420 KB
023.txt 130 ms 24860 KB
024.txt 131 ms 27276 KB
025.txt 128 ms 26264 KB
026.txt 142 ms 25820 KB
027.txt 134 ms 25612 KB
028.txt 131 ms 23876 KB
029.txt 130 ms 24040 KB
030.txt 135 ms 25576 KB
031.txt 142 ms 25704 KB
032.txt 154 ms 27228 KB
033.txt 166 ms 24416 KB
034.txt 185 ms 28096 KB
035.txt 175 ms 26408 KB
036.txt 197 ms 25124 KB
example0.txt 70 ms 18260 KB
example1.txt 68 ms 19412 KB