# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
994960 | 2024-06-08T08:55:07 Z | salmon | Trains (BOI24_trains) | C++14 | 180 ms | 248892 KB |
#include <bits/stdc++.h> using namespace std; vector<int> v; map<int,long long int> mep[100100]; vector<int> rebove[100100]; int N; long long int d,x; vector<pair<int,int>> iv; long long int num[100100]; long long int mod = 1'000'000'007; const int B = 300; long long int blom[100100][B + 5]; int main(){ scanf(" %d",&N); for(int i = 0; i < N; i++){ scanf(" %lld",&d); scanf(" %lld",&x); iv.push_back({d,x}); num[i] = 0; if(d <= B) rebove[min((long long int)N,i + d * x)].push_back(i); } num[0]= 1; long long int sum = 0; for(int i = 0; i < N; i++){ num[i] %= mod; for(int j : rebove[i]){ blom[i][iv[j].first] -= num[j]; blom[i][iv[j].first] %= mod; } if(iv[i].first <= B){ blom[i][iv[i].first] += num[i]; blom[i][iv[i].first] %= mod; } else{ int d = iv[i].first; int x = iv[i].second; for(int j = 1; j <= x && i + j * d < N; j++){ num[i + j * d] += num[i]; } } for(int j = 1; j <= B; j++){ num[min(N,i + j)] += blom[i][j]; blom[min(N,i + j)][j] += blom[i][j]; blom[min(N,i + j)][j] %= mod; } sum = (sum + num[i]) % mod; } printf("%lld",sum); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 9052 KB | Output is correct |
2 | Correct | 1 ms | 9052 KB | Output is correct |
3 | Correct | 1 ms | 9052 KB | Output is correct |
4 | Correct | 1 ms | 9052 KB | Output is correct |
5 | Correct | 2 ms | 9052 KB | Output is correct |
6 | Correct | 1 ms | 9052 KB | Output is correct |
7 | Correct | 2 ms | 9052 KB | Output is correct |
8 | Correct | 2 ms | 9052 KB | Output is correct |
9 | Correct | 2 ms | 9052 KB | Output is correct |
10 | Correct | 1 ms | 9052 KB | Output is correct |
11 | Correct | 2 ms | 9052 KB | Output is correct |
12 | Correct | 1 ms | 9052 KB | Output is correct |
13 | Correct | 2 ms | 9052 KB | Output is correct |
14 | Correct | 1 ms | 9052 KB | Output is correct |
15 | Correct | 1 ms | 9048 KB | Output is correct |
16 | Correct | 1 ms | 9052 KB | Output is correct |
17 | Correct | 2 ms | 9052 KB | Output is correct |
18 | Correct | 1 ms | 9052 KB | Output is correct |
19 | Correct | 2 ms | 9052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 9052 KB | Output is correct |
2 | Correct | 1 ms | 9052 KB | Output is correct |
3 | Correct | 1 ms | 9052 KB | Output is correct |
4 | Correct | 1 ms | 9052 KB | Output is correct |
5 | Correct | 2 ms | 9052 KB | Output is correct |
6 | Correct | 1 ms | 9052 KB | Output is correct |
7 | Correct | 2 ms | 9052 KB | Output is correct |
8 | Correct | 2 ms | 9052 KB | Output is correct |
9 | Correct | 2 ms | 9052 KB | Output is correct |
10 | Correct | 1 ms | 9052 KB | Output is correct |
11 | Correct | 2 ms | 9052 KB | Output is correct |
12 | Correct | 1 ms | 9052 KB | Output is correct |
13 | Correct | 2 ms | 9052 KB | Output is correct |
14 | Correct | 1 ms | 9052 KB | Output is correct |
15 | Correct | 1 ms | 9048 KB | Output is correct |
16 | Correct | 1 ms | 9052 KB | Output is correct |
17 | Correct | 2 ms | 9052 KB | Output is correct |
18 | Correct | 1 ms | 9052 KB | Output is correct |
19 | Correct | 2 ms | 9052 KB | Output is correct |
20 | Incorrect | 20 ms | 29008 KB | Output isn't correct |
21 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 9052 KB | Output is correct |
2 | Correct | 14 ms | 24412 KB | Output is correct |
3 | Incorrect | 10 ms | 19804 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 97 ms | 124660 KB | Output is correct |
2 | Correct | 81 ms | 105160 KB | Output is correct |
3 | Correct | 180 ms | 248776 KB | Output is correct |
4 | Correct | 130 ms | 181192 KB | Output is correct |
5 | Correct | 2 ms | 9048 KB | Output is correct |
6 | Correct | 2 ms | 9052 KB | Output is correct |
7 | Correct | 19 ms | 33116 KB | Output is correct |
8 | Correct | 179 ms | 248892 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 9052 KB | Output is correct |
2 | Correct | 1 ms | 9052 KB | Output is correct |
3 | Correct | 1 ms | 9052 KB | Output is correct |
4 | Correct | 1 ms | 9052 KB | Output is correct |
5 | Correct | 2 ms | 9052 KB | Output is correct |
6 | Correct | 1 ms | 9052 KB | Output is correct |
7 | Correct | 2 ms | 9052 KB | Output is correct |
8 | Correct | 2 ms | 9052 KB | Output is correct |
9 | Correct | 2 ms | 9052 KB | Output is correct |
10 | Correct | 1 ms | 9052 KB | Output is correct |
11 | Correct | 2 ms | 9052 KB | Output is correct |
12 | Correct | 1 ms | 9052 KB | Output is correct |
13 | Correct | 2 ms | 9052 KB | Output is correct |
14 | Correct | 1 ms | 9052 KB | Output is correct |
15 | Correct | 1 ms | 9048 KB | Output is correct |
16 | Correct | 1 ms | 9052 KB | Output is correct |
17 | Correct | 2 ms | 9052 KB | Output is correct |
18 | Correct | 1 ms | 9052 KB | Output is correct |
19 | Correct | 2 ms | 9052 KB | Output is correct |
20 | Incorrect | 20 ms | 29008 KB | Output isn't correct |
21 | Halted | 0 ms | 0 KB | - |