# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
995473 | 2024-06-09T06:56:32 Z | 12345678 | Trains (BOI24_trains) | C++17 | 107 ms | 5980 KB |
#include <bits/stdc++.h> using namespace std; const int nx=1e5+5, mod=1e9+7, kx=255; int n, d[nx], x[nx], qs[kx][kx], dp[nx], res, sm=1, k=250; vector<int> rem[nx]; void add(int idx) { if (d[idx]==0) return; if (d[idx]>k) { for (int i=idx+d[i], j=0; j<x[idx]&&i<=n; j++, i+=d[i]) dp[i]=(dp[i]+dp[idx])%mod; } else { qs[d[idx]][idx%d[idx]]=(qs[d[idx]][idx%d[idx]]+dp[idx])%mod; if (idx+x[idx]*d[idx]<=n) rem[idx+x[idx]*d[idx]].push_back(idx); } } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n; for (int i=1; i<=n; i++) cin>>d[i]>>x[i]; dp[1]=1; add(1); for (int i=2; i<=n; i++) { for (int j=1; j<=k; j++) dp[i]=(dp[i]+qs[j][i%j])%mod; add(i); for (auto idx:rem[i]) qs[d[idx]][idx%d[idx]]=(((qs[d[idx]][idx%d[idx]]-dp[idx])%mod)+mod)%mod; } for (int i=1; i<=n; i++) res=(res+dp[i])%mod; cout<<res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Correct | 1 ms | 2652 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 | 2652 KB | Output is correct |
8 | Incorrect | 1 ms | 2652 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Correct | 1 ms | 2652 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 | 2652 KB | Output is correct |
8 | Incorrect | 1 ms | 2652 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2648 KB | Output is correct |
2 | Correct | 10 ms | 2904 KB | Output is correct |
3 | Correct | 5 ms | 2652 KB | Output is correct |
4 | Correct | 10 ms | 2916 KB | Output is correct |
5 | Correct | 81 ms | 5276 KB | Output is correct |
6 | Correct | 106 ms | 3924 KB | Output is correct |
7 | Correct | 107 ms | 4432 KB | Output is correct |
8 | Incorrect | 1 ms | 2648 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 8 ms | 5980 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Correct | 1 ms | 2652 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 | 2652 KB | Output is correct |
8 | Incorrect | 1 ms | 2652 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |