Submission #1076060
Source Code Expand
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.StringTokenizer; import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); TaskE solver = new TaskE(); solver.solve(1, in, out); out.close(); } static class TaskE { static final int MODULO = (int) (1e9 + 7); public void solve(int testNumber, InputReader in, PrintWriter out) { int zeroes = in.nextInt(); int ones = in.nextInt(); int k = in.nextInt(); int depth = (zeroes + ones - 1) / (k - 1); int[] ways = new int[ones + 1]; ways[0] = 1; long res = 0; boolean[] nice = new boolean[ones + 1]; for (int i = 1; i <= depth; ++i) { Arrays.fill(nice, false); for (int extra = 0; i + extra <= depth; ++extra) { int now = ones - extra * (k - 1); if (now >= 0) { nice[now] = true; } } for (int old = ones; old >= 0; --old) if (ways[old] != 0) { for (int cur = 1; cur < k && old + cur <= ones; ++cur) { if (nice[old + cur]) { res += ways[old]; if (res >= MODULO) res -= MODULO; } ways[old + cur] += ways[old]; if (ways[old + cur] >= MODULO) ways[old + cur] -= MODULO; } } } out.println(res); } } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } }
Submission Info
Submission Time | |
---|---|
Task | E - Eternal Average |
User | Petr |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1600 |
Code Size | 2996 Byte |
Status | AC |
Exec Time | 229 ms |
Memory | 9384 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1600 / 1600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt, s3.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, s1.txt, s2.txt, s3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 100 ms | 8404 KB |
02.txt | AC | 229 ms | 9276 KB |
03.txt | AC | 100 ms | 8528 KB |
04.txt | AC | 100 ms | 8400 KB |
05.txt | AC | 192 ms | 9276 KB |
06.txt | AC | 134 ms | 9296 KB |
07.txt | AC | 112 ms | 8528 KB |
08.txt | AC | 120 ms | 8912 KB |
09.txt | AC | 160 ms | 9296 KB |
10.txt | AC | 155 ms | 9168 KB |
11.txt | AC | 144 ms | 9136 KB |
12.txt | AC | 131 ms | 9040 KB |
13.txt | AC | 145 ms | 8912 KB |
14.txt | AC | 130 ms | 9168 KB |
15.txt | AC | 146 ms | 8912 KB |
16.txt | AC | 99 ms | 8400 KB |
17.txt | AC | 148 ms | 9384 KB |
18.txt | AC | 140 ms | 9168 KB |
19.txt | AC | 135 ms | 9172 KB |
20.txt | AC | 166 ms | 9268 KB |
21.txt | AC | 105 ms | 8400 KB |
22.txt | AC | 194 ms | 9140 KB |
23.txt | AC | 146 ms | 9044 KB |
24.txt | AC | 143 ms | 9172 KB |
s1.txt | AC | 97 ms | 8404 KB |
s2.txt | AC | 102 ms | 8400 KB |
s3.txt | AC | 100 ms | 8400 KB |