Submission #2527601
Source Code Expand
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { int h, w; int[][] board; Triplet[] series; int MOD = 1000000007; public static void main(String args[]) { new Main().run(); } void run() { FastReader sc = new FastReader(); h = sc.nextInt(); w = sc.nextInt(); board = new int[h][w]; series = new Triplet[h * w]; int index = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { board[i][j] = sc.nextInt(); series[index] = new Triplet(i, j, board[i][j]); index++; } } solve(); } void solve() { long[][] dp = new long[h][w]; Arrays.sort(series); for (int i = 0; i < series.length; i++) { int y = series[i].y; int x = series[i].x; int value = series[i].value; dp[y][x] = 1; if (x > 0 && board[y][x - 1] < board[y][x]) { dp[y][x] += dp[y][x - 1]; dp[y][x] %= MOD; } if (x < w - 1 && board[y][x + 1] < board[y][x]) { dp[y][x] += dp[y][x + 1]; dp[y][x] %= MOD; } if (y > 0 && board[y - 1][x] < board[y][x]) { dp[y][x] += dp[y - 1][x]; dp[y][x] %= MOD; } if (y < h - 1 && board[y + 1][x] < board[y][x]) { dp[y][x] += dp[y + 1][x]; dp[y][x] %= MOD; } } long sum = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { sum += dp[i][j]; sum %= MOD; } } System.out.println(sum); } class Triplet implements Comparable<Triplet> { int y; int x; int value; Triplet(int y, int x, int value) { this.y = y; this.x = x; this.value = value; } public int compareTo(Triplet t) { return this.value - t.value; } } static class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine() { String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } }
Submission Info
Submission Time | |
---|---|
Task | D - 経路 |
User | ynish |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 3525 Byte |
Status | AC |
Exec Time | 1809 ms |
Memory | 141432 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, sample01.txt, sample02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00.txt | AC | 1037 ms | 112372 KB |
01.txt | AC | 539 ms | 103924 KB |
02.txt | AC | 919 ms | 112776 KB |
03.txt | AC | 69 ms | 19412 KB |
04.txt | AC | 70 ms | 16084 KB |
05.txt | AC | 80 ms | 20692 KB |
06.txt | AC | 80 ms | 19028 KB |
07.txt | AC | 81 ms | 18644 KB |
08.txt | AC | 85 ms | 17364 KB |
09.txt | AC | 70 ms | 21460 KB |
10.txt | AC | 103 ms | 21460 KB |
11.txt | AC | 1613 ms | 136212 KB |
12.txt | AC | 1669 ms | 141432 KB |
13.txt | AC | 1772 ms | 138880 KB |
14.txt | AC | 1686 ms | 136852 KB |
15.txt | AC | 1208 ms | 115908 KB |
16.txt | AC | 1809 ms | 137304 KB |
17.txt | AC | 1611 ms | 138688 KB |
18.txt | AC | 893 ms | 111508 KB |
19.txt | AC | 575 ms | 111372 KB |
sample01.txt | AC | 69 ms | 18644 KB |
sample02.txt | AC | 73 ms | 19412 KB |