Submission #923965
Source Code Expand
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; import java.util.function.BiFunction; public class Main { Scanner sc = new Scanner(System.in); public static void main(String[] args) { new Main().run(); } int[][] ofs = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} }; int h, w; int[][] field; long MOD = 1_000_000_007; long[][] dp; boolean[][] done; long dfs(int x, int y) { if (done[y][x]) { return dp[y][x]; } long sum = 1; for (int i = 0; i < 4; ++i) { int nx = x + ofs[i][0]; int ny = y + ofs[i][1]; if (field[ny][nx] == 0) { continue; } if (field[y][x] >= field[ny][nx]) { continue; } sum += dfs(nx, ny); sum %= MOD; } dp[y][x] = sum; done[y][x] = true; return sum; } void run() { int h = ni(); int w = ni(); field = new int[h + 2][w + 2]; dp = new long[h + 2][w + 2]; done = new boolean[h + 2][w + 2]; for (int i = 1; i <= h; ++i) { for (int j = 1; j <= w; ++j) { field[i][j] = ni(); } } long sum = 0; for (int i = 1; i <= h; ++i) { for (int j = 1; j <= w; ++j) { sum += dfs(j, i); sum %= MOD; } } System.out.println(sum); } int ni() { return Integer.parseInt(sc.next()); } void debug(Object... os) { System.err.println(Arrays.deepToString(os)); } class BIT<T> { int n; ArrayList<T> bit; BiFunction<T, T, T> bif; BIT(int n, BiFunction<T, T, T> bif, T defaultValue) { this.n = n; bit = new ArrayList<>(n + 1); for (int i = 0; i < n + 1; ++i) { bit.add(defaultValue); } this.bif = bif; } void update(int i, T v) { for (int x = i; x <= n; x += x & -x) { bit.set(x, bif.apply(bit.get(x), v)); } } T reduce(int i, T defaultValue) { T ret = defaultValue; for (int x = i; x > 0; x -= x & -x) { ret = bif.apply(ret, bit.get(x)); } return ret; } } }
Submission Info
Submission Time | |
---|---|
Task | D - 経路 |
User | arukuka |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 2179 Byte |
Status | AC |
Exec Time | 1113 ms |
Memory | 136644 KB |
Judge Result
Set Name | sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample01.txt, sample02.txt |
All | 00.txt, 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, sample01.txt, sample02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00.txt | AC | 895 ms | 105548 KB |
01.txt | AC | 989 ms | 120828 KB |
02.txt | AC | 834 ms | 104108 KB |
03.txt | AC | 126 ms | 9552 KB |
04.txt | AC | 126 ms | 9548 KB |
05.txt | AC | 132 ms | 9680 KB |
06.txt | AC | 160 ms | 10444 KB |
07.txt | AC | 160 ms | 10448 KB |
08.txt | AC | 146 ms | 10064 KB |
09.txt | AC | 127 ms | 9544 KB |
10.txt | AC | 166 ms | 11856 KB |
11.txt | AC | 1093 ms | 136644 KB |
12.txt | AC | 1049 ms | 134288 KB |
13.txt | AC | 1084 ms | 135000 KB |
14.txt | AC | 1113 ms | 136128 KB |
15.txt | AC | 1082 ms | 125836 KB |
16.txt | AC | 1062 ms | 134048 KB |
17.txt | AC | 1069 ms | 135380 KB |
18.txt | AC | 833 ms | 105864 KB |
19.txt | AC | 790 ms | 104072 KB |
sample01.txt | AC | 126 ms | 9556 KB |
sample02.txt | AC | 127 ms | 9556 KB |