Submission #1668036


Source Code Expand

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

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

    void solve() {
        final int mod = (int) 1e9 + 7;
        final int M = 2222;
        int[][] c = new int[M][M];
        c[0][0] = 1;
        for (int i = 1; i < M; i++) {
            c[i][0] = 1;
            for (int j = 1; j < M; j++) {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
                if (c[i][j] >= mod) {
                    c[i][j] -= mod;
                }
            }
        }
        int[] pow2 = new int[M];
        pow2[0] = 1;
        for (int i = 1; i < M; i++) {
            pow2[i] = pow2[i - 1] + pow2[i - 1];
            if (pow2[i] >= mod) {
                pow2[i] -= mod;
            }
        }
        long[][] dp2 = new long[M][M];
        for (int x = 0; x < M; x++) {
            for (int y = 0; y < M; y++) {
                if (x == 0 || y == 0) {
                    dp2[x][y] = 1;
                } else {
                    dp2[x][y] = dp2[x - 1][y - 1] + dp2[x][y - 1];
                    if (dp2[x][y] >= mod) {
                        dp2[x][y] -= mod;
                    }
                }
            }
        }
        long[][] dp2Pref = new long[M][M];
        for (int x = 0; x < M; x++) {
            for (int y = 0; y < M; y++) {
                dp2Pref[x][y] = dp2[x][y];
                if (x > 0) {
                    dp2Pref[x][y] += dp2Pref[x - 1][y];
                    if (dp2Pref[x][y] >= mod) {
                        dp2Pref[x][y] -= mod;
                    }
                }
            }
        }
        int[][] dp = new int[M][M];
        for (int red = 0; red < M; red++) {
            for (int blue = 0; blue < M; blue++) {
                if (red == 0 || blue == 0) {
                    dp[red][blue] = 1;
                } else {
                    dp[red][blue] += dp2Pref[red][blue - 1];
                    if (dp[red][blue] >= mod) {
                        dp[red][blue] -= mod;
                    }
                }
            }
        }
        long res = 0;
        int a = in.nextInt();
        int b = in.nextInt();
        for (int startRed = 0; startRed <= a; startRed++) {
            for (int cntBlue = 1; cntBlue <= b; cntBlue++) {
                int curC = c[b - 1][cntBlue - 1];
                int redStay = a - startRed - (b - cntBlue);
                if (redStay < 0) {
                    continue;
                }
                long add = curC * 1L * dp[redStay][b - cntBlue] % mod;
                res += add;
            }
        }
        out.println(res % mod);
    }

    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 E - Popping Balls
User qwerty787788
Language Java8 (OpenJDK 1.8.0)
Score 1600
Code Size 4889 Byte
Status
Exec Time 360 ms
Memory 169160 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt, example2.txt, example3.txt
All 1600 / 1600 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, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, example0.txt, example1.txt, example2.txt, example3.txt
Case Name Status Exec Time Memory
000.txt 360 ms 162736 KB
001.txt 309 ms 162752 KB
002.txt 312 ms 164036 KB
003.txt 312 ms 165976 KB
004.txt 358 ms 163632 KB
005.txt 352 ms 162072 KB
006.txt 352 ms 163128 KB
007.txt 355 ms 165184 KB
008.txt 352 ms 166608 KB
009.txt 354 ms 161744 KB
010.txt 352 ms 167184 KB
011.txt 359 ms 168392 KB
012.txt 358 ms 162224 KB
013.txt 353 ms 167204 KB
014.txt 330 ms 160952 KB
015.txt 327 ms 162748 KB
016.txt 314 ms 162848 KB
017.txt 314 ms 162956 KB
018.txt 310 ms 165916 KB
019.txt 308 ms 163272 KB
020.txt 320 ms 166048 KB
021.txt 307 ms 164116 KB
022.txt 323 ms 165560 KB
023.txt 313 ms 161592 KB
024.txt 330 ms 163508 KB
025.txt 313 ms 165068 KB
026.txt 330 ms 166088 KB
027.txt 315 ms 166228 KB
028.txt 339 ms 162760 KB
029.txt 310 ms 162740 KB
030.txt 311 ms 162964 KB
031.txt 313 ms 163408 KB
032.txt 306 ms 168080 KB
033.txt 334 ms 166476 KB
034.txt 313 ms 164012 KB
035.txt 316 ms 164020 KB
036.txt 316 ms 163740 KB
037.txt 303 ms 169160 KB
038.txt 323 ms 162104 KB
039.txt 312 ms 160692 KB
040.txt 316 ms 161968 KB
041.txt 313 ms 163524 KB
042.txt 311 ms 162232 KB
043.txt 312 ms 163780 KB
example0.txt 315 ms 164032 KB
example1.txt 313 ms 164508 KB
example2.txt 310 ms 168764 KB
example3.txt 348 ms 160440 KB