oj.uz

Submission #994582

# Submission time Handle Problem Language Result Execution time Memory
994582 2024-06-08T01:56:39 Z PenguinsAreCute Trains (BOI24_trains) C++17
16 / 100
 192 ms 124068 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int SQ = 313;
const int MOD = 1e9 + 7;
main() {
	int n; cin >> n;
	int d[n], x[n]; for(int i=0;i<n;i++) cin>>d[i]>>x[i];
	int dp[n], pre[n][SQ];
	for(int i=n;i--;) {
		dp[i]=1;
		if(d[i]>=SQ) for(int j=1;j<=x[i]&&i+j*d[i]<n;j++) {dp[i]+=dp[i+j*d[i]]; if(dp[i]>=MOD) dp[i]-=MOD;}
		else if(d[i]) {
			if(i+d[i]<n) dp[i]+=pre[i+d[i]][d[i]];
			if(i+d[i]*(x[i]+1)<n) dp[i]-=pre[i+d[i]*(x[i]+1)][d[i]];
			if(dp[i]>=MOD) dp[i]-=MOD;
			if(dp[i]<0) dp[i]+=MOD;
		}
		for(int j=1;j<SQ;j++) {pre[i][j]=dp[i]+(i+j<n?pre[i+j][j]:0); if(pre[i][j]>=MOD) pre[i][j]-=MOD;}
	}
	cout << dp[0];
}

Compilation message

Main.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main() {
      | ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 344 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 344 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 11 ms 8284 KB Output is correct
3 Correct 8 ms 5980 KB Output is correct
4 Correct 15 ms 10844 KB Output is correct
5 Correct 135 ms 95828 KB Output is correct
6 Correct 182 ms 123984 KB Output is correct
7 Correct 189 ms 124068 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 19 ms 12792 KB Output is correct
12 Correct 192 ms 123984 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 23 ms 12620 KB Output is correct
15 Correct 190 ms 123988 KB Output is correct

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 121176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 344 KB Output isn't correct
12 Halted 0 ms 0 KB -