Submission #480708

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
480708	2021-10-17T22:52:23 Z	Toinfinity1	Jump (BOI06_jump)	Java 11	100 / 100	290 ms	14508 KB

jump

import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class jump
{
	static class InputReader {
		BufferedReader reader;
		StringTokenizer tokenizer;
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
		String next() { // reads in the next string
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() { // reads in the next int
			return Integer.parseInt(next());
		}
		public long nextLong() { // reads in the next long
			return Long.parseLong(next());
		}
		public double nextDouble() { // reads in the next double
			return Double.parseDouble(next());
			}
		}
	static InputReader r = new InputReader(System.in);
	static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args)
	{
		int n = r.nextInt();
		BigInteger[][] dp = new BigInteger[n][n];
		int[][] grid = new int[n][n];
		for (int i = 0; i < n; i ++)
		{
			for (int j = 0; j < n; j ++)
			{
				dp[i][j] = new BigInteger("0");
			}
		}
		for (int i = 0; i < n; i ++)
		{
			for (int j = 0; j < n; j ++)
			{
				grid[i][j] = r.nextInt();
			}
		}
		for (int i = n - 1; i >= 0; i --)
		{
			for (int j = n - 1; j >= 0; j --)
			{
				if (grid[i][j] + i <= n - 1)
				{
					dp[i][j] = dp[i+grid[i][j]][j];
				}
				if (grid[i][j] + j <= n - 1)
				{
					dp[i][j] = dp[i][j].add(dp[i][j+grid[i][j]]);
				}
				if (i== n - 1 && j == n - 1)
				{
					dp[i][j] = new BigInteger("1");
				}
				
			}
		}
		pw.println(dp[0][0]);
		pw.close();
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	8644 KB	Output is correct
2	Correct	71 ms	8688 KB	Output is correct
3	Correct	67 ms	8376 KB	Output is correct
4	Correct	68 ms	8340 KB	Output is correct
5	Correct	70 ms	8720 KB	Output is correct
6	Correct	89 ms	8572 KB	Output is correct
7	Correct	74 ms	8728 KB	Output is correct
8	Correct	82 ms	8512 KB	Output is correct
9	Correct	95 ms	8720 KB	Output is correct
10	Correct	88 ms	8508 KB	Output is correct
11	Correct	83 ms	8684 KB	Output is correct
12	Correct	84 ms	8556 KB	Output is correct
13	Correct	88 ms	8472 KB	Output is correct
14	Correct	90 ms	8820 KB	Output is correct
15	Correct	108 ms	9068 KB	Output is correct
16	Correct	188 ms	10992 KB	Output is correct
17	Correct	193 ms	10876 KB	Output is correct
18	Correct	225 ms	13000 KB	Output is correct
19	Correct	212 ms	12444 KB	Output is correct
20	Correct	290 ms	14508 KB	Output is correct