Submission #1013586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013586		rainboy	Trains (BOI24_trains)	C11	100 / 100	121 ms	127432 KiB

Main

#include <stdio.h>

#define N	100000
#define D	316	/* D = floor(sqrt(N)) */
#define MD	1000000007

int main() {
	static int dd[N], ll[N], dp[N], dq[N][D + 1];
	int n, i, j, d, l, k;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &dd[i], &ll[i]);
	for (i = n - 1; i >= 0; i--) {
		d = dd[i], l = ll[i];
		if (d == 0 || l == 0)
			dp[i] = 1;
		else if (d <= D)
			dp[i] = ((i + d < n ? dq[i + d][d] : 0) - (l < (n - 1 - i) / d ? dq[i + d * (l + 1)][d] : 0) + 1 + MD) % MD;
		else {
			dp[i] = 1;
			for (k = 1; k <= l && (j = i + d * k) < n; k++)
				dp[i] = (dp[i] + dp[j]) % MD;
		}
		for (d = 1; d <= D; d++)
			dq[i][d] = ((i + d < n ? dq[i + d][d] : 0) + dp[i]) % MD;
	}
	printf("%d\n", dp[0]);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:11:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:13:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d%d", &dd[i], &ll[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29