| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1052893 |
2024-08-11T05:37:58 Z |
vjudge1 |
Trains (BOI24_trains) |
C++17 |
|
48 ms |
6744 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10, mod = 1e9 + 7, D = 100;
ll n, dp[N], sm[D][D], a[N][2];
vector<ll> del[N];
void add(ll &x, ll y){
x += y;
if (x < 0) x += mod;
if (x >= mod) x -= mod;
}
int main(){
cin >> n;
for (ll i = 1; i <= n; i ++)
cin >> a[i][0] >> a[i][1];
dp[1] = 1;
for (ll i = 1; i <= n; i ++){
for (ll d = 1; d < D; d ++)
add(dp[i], sm[d][i % d]);
for (ll l : del[i])
add(sm[a[l][0]][l % a[l][0]], -dp[l]);
if (!a[i][0]) continue;
if (a[i][0] >= D){
for (ll j = i + a[i][0]; j <= n and a[i][1]; j += a[i][0], a[i][1]--)
add(dp[j], dp[i]);
}
else{
add(sm[a[i][0]][i % a[i][0]], dp[i]);
ll r = 1ll * i + 1ll * a[i][0] * a[i][1];
if (r <= n)
del[r].push_back(i);
}
}
ll ans = 0;
for (ll i = 1; i <= n; i ++)
add(ans, dp[i]);
ans %= mod;
ans += mod;
ans %= mod;
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4700 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4700 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4764 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4952 KB |
Output is correct |
| 5 |
Correct |
28 ms |
6744 KB |
Output is correct |
| 6 |
Correct |
42 ms |
5200 KB |
Output is correct |
| 7 |
Correct |
42 ms |
5228 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
19 ms |
4720 KB |
Output is correct |
| 3 |
Correct |
48 ms |
5104 KB |
Output is correct |
| 4 |
Correct |
35 ms |
4976 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 7 |
Correct |
5 ms |
4700 KB |
Output is correct |
| 8 |
Correct |
48 ms |
4988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4700 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
