Submission #171728


Source Code Expand

Copy
import static java.util.Arrays.*;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	long MOD = 1000000007;

	Scanner sc = new Scanner(System.in);
	void run() {
		int n = sc.nextInt();
		long[] a = new long[n];
		for (int i = 0; i < n; i++) a[i] = sc.nextLong();

		long ans = 1;
		int prev = -1;
		for (int i = 0; i < n; i++) {
			if (a[i] != -1) {
				if (prev != -1) {
//					tr(a[prev], a[i], i - prev - 1);
					long cur = calc((int)(i - prev - 1), (int)(a[i] - a[prev]));
					ans *= cur;
					ans %= MOD;
				}
				prev = i;
			}
		}
		System.out.println(ans);
	}

	long dp[] = new long[2014];

	long calc(int N, int M) {
		if (M >= dp.length) return 0;
		fill(dp, 0);
		dp[0] = 1;
		for (int n = 0; n < N; n++) {
			for (int m = 1; m <= M; m++) {
				dp[m] += dp[m - 1];
				if (dp[m] >= MOD)
					dp[m] -= MOD;
			}
		}
		long res = 0;
		for (int i = 0; i <= M; i++)
			res += dp[i];
		return res % MOD;
	}

	static void tr(Object... os) {
		System.err.println(deepToString(os));
	}


}

Submission Info

Submission Time
Task C - タコヤ木
User hs484
Language Java (OpenJDK 1.7.0)
Score 80
Code Size 1118 Byte
Status WA
Exec Time 620 ms
Memory 26776 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 50 / 50 30 / 30 0 / 20
Status
AC × 2
WA × 1
AC × 14
AC × 26
AC × 26
WA × 10
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 485 ms 23248 KB
sample_02.txt AC 450 ms 23252 KB
sample_03.txt WA 456 ms 23252 KB
subtask1_01.txt AC 447 ms 23260 KB
subtask1_02.txt AC 442 ms 23140 KB
subtask1_03.txt AC 442 ms 23268 KB
subtask1_04.txt AC 514 ms 23520 KB
subtask1_05.txt AC 463 ms 23400 KB
subtask1_06.txt AC 468 ms 23388 KB
subtask1_07.txt AC 514 ms 23404 KB
subtask1_08.txt AC 469 ms 23724 KB
subtask1_09.txt AC 468 ms 23652 KB
subtask1_10.txt AC 470 ms 23392 KB
subtask1_11.txt AC 475 ms 23388 KB
subtask1_12.txt AC 493 ms 23772 KB
subtask2_01.txt AC 457 ms 23264 KB
subtask2_02.txt AC 447 ms 23260 KB
subtask2_03.txt AC 453 ms 23256 KB
subtask2_04.txt AC 504 ms 24028 KB
subtask2_05.txt AC 556 ms 24796 KB
subtask2_06.txt AC 488 ms 24288 KB
subtask2_07.txt AC 609 ms 25816 KB
subtask2_08.txt AC 614 ms 25952 KB
subtask2_09.txt AC 556 ms 25696 KB
subtask2_10.txt AC 570 ms 26456 KB
subtask2_11.txt AC 605 ms 26436 KB
subtask2_12.txt AC 566 ms 25728 KB
subtask3_01.txt WA 455 ms 23140 KB
subtask3_02.txt WA 461 ms 23252 KB
subtask3_03.txt WA 452 ms 23260 KB
subtask3_04.txt WA 578 ms 26656 KB
subtask3_05.txt WA 489 ms 23908 KB
subtask3_06.txt WA 587 ms 26464 KB
subtask3_07.txt AC 556 ms 25700 KB
subtask3_08.txt WA 589 ms 26776 KB
subtask3_09.txt AC 602 ms 25728 KB
subtask3_10.txt WA 620 ms 26768 KB
subtask3_11.txt WA 563 ms 26328 KB
subtask3_12.txt WA 616 ms 26580 KB