oj.uz

Submission #1000146

# Submission time Handle Problem Language Result Execution time Memory
1000146 2024-06-16T17:44:47 Z OAleksa Trains (BOI24_trains) C++14
21 / 100
 2000 ms 5128 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 1e5 + 69;
const int B = 1;
const int mod = 1e9 + 7;
int n, d[N], x[N], dp[N];
vector<int> cnt[B];
vector<tuple<int, int, int>> who[N];
int add(int x, int y) {
	x += y;
	if (x >= mod)
		x -= mod;
	return x;
}
int sub(int x, int y) {
	x -= y;
	x = (x + 1000ll * mod) % mod;
	return x;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--) {
		cin >> n;
		for (int i = 1;i <= n;i++) {
			cin >> d[i] >> x[i];
			x[i] = min(x[i], n);
		}
		for (int i = 1;i < B;i++)
			cnt[i].resize(i);
		dp[1] = 1;
		for (int i = 1;i <= n;i++) {
			if (d[i] >= B) {
				for (int j = i + d[i], j1 = 1;j <= n && j1 <= x[i];j += d[i], j1++) {
					dp[j] = add(dp[j], dp[i]);
				}
			}
			else {
				for (int j = 1;j < B;j++) {
					int x = i % j;
					dp[i] = add(dp[i], cnt[j][x]);
				}
				if (d[i] != 0) {
					int when = i + x[i] * d[i];
					if (when <= n) 
						who[when].push_back({d[i], i % d[i], dp[i]});
					cnt[d[i]][i % d[i]] = add(cnt[d[i]][i % d[i]], dp[i]);
				}
			}
			for (auto j : who[i]) {
				int a, b, c;
				tie(a, b, c) = j;
				cnt[a][b] = sub(cnt[a][b], c);
			}
		}
		int ans = 0;
		for (int i = 1;i <= n;i++)
			ans = add(ans, dp[i]);
		cout << ans;
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 4588 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 4588 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 4 ms 4696 KB Output is correct
21 Correct 2 ms 4700 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 15 ms 2908 KB Output is correct
24 Correct 1 ms 2908 KB Output is correct
25 Correct 3 ms 2908 KB Output is correct
26 Correct 8 ms 2908 KB Output is correct
27 Correct 28 ms 3028 KB Output is correct
28 Correct 7 ms 2908 KB Output is correct
29 Correct 37 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct
31 Correct 20 ms 2908 KB Output is correct
32 Correct 38 ms 4700 KB Output is correct
33 Correct 2 ms 4700 KB Output is correct
34 Correct 2 ms 4700 KB Output is correct
35 Correct 2 ms 4700 KB Output is correct
36 Correct 4 ms 2908 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 14 ms 4700 KB Output is correct
3 Correct 8 ms 4700 KB Output is correct
4 Correct 28 ms 4748 KB Output is correct
5 Correct 7 ms 4956 KB Output is correct
6 Execution timed out 2097 ms 5028 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 3928 KB Output is correct
2 Correct 199 ms 4728 KB Output is correct
3 Correct 1613 ms 5128 KB Output is correct
4 Correct 915 ms 4916 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 56 ms 3036 KB Output is correct
8 Execution timed out 2082 ms 4956 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 4588 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 4 ms 4696 KB Output is correct
21 Correct 2 ms 4700 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 15 ms 2908 KB Output is correct
24 Correct 1 ms 2908 KB Output is correct
25 Correct 3 ms 2908 KB Output is correct
26 Correct 8 ms 2908 KB Output is correct
27 Correct 28 ms 3028 KB Output is correct
28 Correct 7 ms 2908 KB Output is correct
29 Correct 37 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct
31 Correct 20 ms 2908 KB Output is correct
32 Correct 38 ms 4700 KB Output is correct
33 Correct 2 ms 4700 KB Output is correct
34 Correct 2 ms 4700 KB Output is correct
35 Correct 2 ms 4700 KB Output is correct
36 Correct 4 ms 2908 KB Output is correct
37 Correct 1 ms 2652 KB Output is correct
38 Correct 14 ms 4700 KB Output is correct
39 Correct 8 ms 4700 KB Output is correct
40 Correct 28 ms 4748 KB Output is correct
41 Correct 7 ms 4956 KB Output is correct
42 Execution timed out 2097 ms 5028 KB Time limit exceeded
43 Halted 0 ms 0 KB -