# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
994956 | 2024-06-08T08:52:24 Z | salmon | Trains (BOI24_trains) | C++14 | 37 ms | 67008 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; 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]; } if(iv[i].first <= B){ blom[i][iv[i].first] += num[i]; } 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]; } sum = (sum + num[i]) % mod; } printf("%lld",sum); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 8536 KB | Output is correct |
2 | Correct | 2 ms | 8540 KB | Output is correct |
3 | Correct | 2 ms | 8540 KB | Output is correct |
4 | Correct | 2 ms | 8540 KB | Output is correct |
5 | Correct | 2 ms | 8540 KB | Output is correct |
6 | Correct | 2 ms | 8540 KB | Output is correct |
7 | Correct | 2 ms | 8540 KB | Output is correct |
8 | Correct | 2 ms | 8536 KB | Output is correct |
9 | Correct | 2 ms | 8540 KB | Output is correct |
10 | Correct | 2 ms | 8540 KB | Output is correct |
11 | Correct | 2 ms | 8540 KB | Output is correct |
12 | Correct | 2 ms | 8540 KB | Output is correct |
13 | Correct | 2 ms | 8540 KB | Output is correct |
14 | Correct | 2 ms | 8540 KB | Output is correct |
15 | Correct | 2 ms | 8540 KB | Output is correct |
16 | Correct | 2 ms | 8540 KB | Output is correct |
17 | Correct | 2 ms | 8540 KB | Output is correct |
18 | Correct | 2 ms | 8540 KB | Output is correct |
19 | Correct | 3 ms | 8540 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 8536 KB | Output is correct |
2 | Correct | 2 ms | 8540 KB | Output is correct |
3 | Correct | 2 ms | 8540 KB | Output is correct |
4 | Correct | 2 ms | 8540 KB | Output is correct |
5 | Correct | 2 ms | 8540 KB | Output is correct |
6 | Correct | 2 ms | 8540 KB | Output is correct |
7 | Correct | 2 ms | 8540 KB | Output is correct |
8 | Correct | 2 ms | 8536 KB | Output is correct |
9 | Correct | 2 ms | 8540 KB | Output is correct |
10 | Correct | 2 ms | 8540 KB | Output is correct |
11 | Correct | 2 ms | 8540 KB | Output is correct |
12 | Correct | 2 ms | 8540 KB | Output is correct |
13 | Correct | 2 ms | 8540 KB | Output is correct |
14 | Correct | 2 ms | 8540 KB | Output is correct |
15 | Correct | 2 ms | 8540 KB | Output is correct |
16 | Correct | 2 ms | 8540 KB | Output is correct |
17 | Correct | 2 ms | 8540 KB | Output is correct |
18 | Correct | 2 ms | 8540 KB | Output is correct |
19 | Correct | 3 ms | 8540 KB | Output is correct |
20 | Incorrect | 8 ms | 19036 KB | Output isn't correct |
21 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 8540 KB | Output is correct |
2 | Incorrect | 7 ms | 16988 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 37 ms | 67008 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 8536 KB | Output is correct |
2 | Correct | 2 ms | 8540 KB | Output is correct |
3 | Correct | 2 ms | 8540 KB | Output is correct |
4 | Correct | 2 ms | 8540 KB | Output is correct |
5 | Correct | 2 ms | 8540 KB | Output is correct |
6 | Correct | 2 ms | 8540 KB | Output is correct |
7 | Correct | 2 ms | 8540 KB | Output is correct |
8 | Correct | 2 ms | 8536 KB | Output is correct |
9 | Correct | 2 ms | 8540 KB | Output is correct |
10 | Correct | 2 ms | 8540 KB | Output is correct |
11 | Correct | 2 ms | 8540 KB | Output is correct |
12 | Correct | 2 ms | 8540 KB | Output is correct |
13 | Correct | 2 ms | 8540 KB | Output is correct |
14 | Correct | 2 ms | 8540 KB | Output is correct |
15 | Correct | 2 ms | 8540 KB | Output is correct |
16 | Correct | 2 ms | 8540 KB | Output is correct |
17 | Correct | 2 ms | 8540 KB | Output is correct |
18 | Correct | 2 ms | 8540 KB | Output is correct |
19 | Correct | 3 ms | 8540 KB | Output is correct |
20 | Incorrect | 8 ms | 19036 KB | Output isn't correct |
21 | Halted | 0 ms | 0 KB | - |