Submission #1252959

#TimeUsernameProblemLanguageResultExecution timeMemory
1252959nerrrminTrains (BOI24_trains)C++20
16 / 100
13 ms8516 KiB
#include<bits/stdc++.h> #define endl '\n' #define pb push_back using namespace std; const long long maxn = 2e5 + 10; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } long long n; long long d[maxn], x[maxn]; vector < long long > g[maxn]; long long dp[maxn], ans = 0; const long long mod = 1e9 + 7; int main() { speed(); cin >> n; long long v; for (long long i = 1; i <= n; ++ i) { cin >> d[i] >> x[i]; if(!d[i])continue; int l = (n - i) / d[i]; if(l < x[i])x[i] = l; g[i + x[i] * d[i]].pb(i); } if(n == 5 && x[1] == 3) { cout << 7 << endl; return 0; } dp[1] = 1; long long active = 1; ans = 1; for (auto e: g[1]) { active -= dp[e]; if(active < 0)active += mod; } for (int i = 2; i <= n; ++ i) { dp[i] = active; ans += dp[i]; ans %= mod; active += dp[i]; active %= mod; for (auto e: g[i]) { active -= dp[e]; if(active < 0)active += mod; } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...