結果
| 問題 | No.498 ワープクリスタル (給料日編) |
| ユーザー |
 37zigen
|
| 提出日時 | 2016-07-13 11:00:52 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 687 ms / 2,000 ms |
| コード長 | 4,397 bytes |
| コンパイル時間 | 2,510 ms |
| コンパイル使用メモリ | 78,888 KB |
| 実行使用メモリ | 175,860 KB |
| 最終ジャッジ日時 | 2024-10-15 19:51:08 |
| 合計ジャッジ時間 | 12,955 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 21 |
ソースコード
import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;public class Main {static void sample() {System.out.println(1 + " " + 1 + " " + 5);for (int i = 0; i < 5; i++) {System.out.println(1 + " " + 1 + " " + 15);}}static long MOD = 1_000_000_000 + 7;static void solver() {long gx = nl();long gy = nl();int k = ni();// the number of crystalslong[] x = new long[k];long[] y = new long[k];long[] n = new long[k];for (int i = 0; i < k; i++) {x[i] = nl();y[i] = nl();n[i] = ni();}memo = new long[16777233];Arrays.fill(memo, -1);long ans = dp(0, 0, x, y, n, gx, gy);if (gx == 0 && gy == 0)ans++;out.println(ans);}static long[] memo;static long dp(long curx, long cury, long[] x, long[] y, long[] n, long gx, long gy) {int idx = 0;for (int i = 0; i < n.length; i++) {idx += pow(16, i) * n[i];}if (idx == 0)return 0;if (memo[idx] != -1) {return memo[idx];} else {long sum = 0;for (int i = 0; i < n.length; i++) {if (n[i] > 0) {long[] d = Arrays.copyOf(n, n.length);d[i]--;long nx = curx + x[i];long ny = cury + y[i];if (gx == nx && gy == ny) {sum += 1;}sum += dp(nx, ny, x, y, d, gx, gy);sum %= MOD;}}memo[idx] = sum % MOD;return sum;}}static InputStream is;static PrintWriter out;static String INPUT = "";public static void main(String[] args) throws Exception {is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);solver();out.flush();}static long nl() {try {long num = 0;boolean minus = false;while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));if (num == '-') {num = 0;minus = true;} else {num -= '0';}while (true) {int b = is.read();if (b >= '0' && b <= '9') {num = num * 10 + (b - '0');} else {return minus ? -num : num;}}} catch (IOException e) {}return -1;}static char nc() {try {int b = skip();if (b == -1)return 0;return (char) b;} catch (IOException e) {}return 0;}static double nd() {try {return Double.parseDouble(ns());} catch (Exception e) {}return 0;}static String ns() {try {int b = skip();StringBuilder sb = new StringBuilder();if (b == -1)return "";sb.append((char) b);while (true) {b = is.read();if (b == -1)return sb.toString();if (b <= ' ')return sb.toString();sb.append((char) b);}} catch (IOException e) {}return "";}public static char[] ns(int n) {char[] buf = new char[n];try {int b = skip(), p = 0;if (b == -1)return null;buf[p++] = (char) b;while (p < n) {b = is.read();if (b == -1 || b <= ' ')break;buf[p++] = (char) b;}return Arrays.copyOf(buf, p);} catch (IOException e) {}return null;}public static byte[] nse(int n) {byte[] buf = new byte[n];try {int b = skip();if (b == -1)return null;is.read(buf);return buf;} catch (IOException e) {}return null;}static int skip() throws IOException {int b;while ((b = is.read()) != -1 && !(b >= 33 && b <= 126));return b;}static boolean eof() {try {is.mark(1000);int b = skip();is.reset();return b == -1;} catch (IOException e) {return true;}}static int ni() {try {int num = 0;boolean minus = false;while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'));if (num == '-') {num = 0;minus = true;} else {num -= '0';}while (true) {int b = is.read();if (b >= '0' && b <= '9') {num = num * 10 + (b - '0');} else {return minus ? -num : num;}}} catch (IOException e) {}return -1;}static void tr(Object... o) {if (INPUT.length() != 0)System.out.println(Arrays.deepToString(o));}static long pow(long a, long n) {long A = a;long ans = 1;while (n >= 1) {if (n % 2 == 0) {A = A * A;n /= 2;} else if (n % 2 == 1) {ans = ans * A;n--;}}return ans;}}