제출 #1253027

#제출 시각아이디문제언어결과실행 시간메모리
1253027nerrrminTrains (BOI24_trains)C++20
58 / 100
170 ms14204 KiB
#include<bits/stdc++.h> #define endl '\n' #define pb push_back using namespace std; const long long maxn = 2e5 + 10, maxx = 555; 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]; vector < pair < long long, long long > >rem[maxn]; long long dp[maxn], act[maxx][maxx], 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; if(d[i] > 400) { for (int j = 1; j <= x[i]; ++ j) { int v = i + j * d[i]; if(v > n)break; g[j].pb(i); } } else { int l = (n - i) / d[i]; if(l < x[i])x[i] = l; rem[i + x[i] * d[i]].pb(make_pair(d[i], i)); } } dp[1] = 1; ans = 1; if(d[1] && d[1] <= 400) { act[d[1]][1 % d[1]] += dp[1]; act[d[1]][1 % d[1]] %= mod; } if(rem[1].size()) { act[d[1]][1 % d[1]] -= dp[1]; act[d[1]][1 % d[1]] %= mod; } for (int i = 2; i <= n; ++ i) { for (auto e: g[i]) { dp[i] += dp[e]; dp[i] %= mod; } for (int r = 1; r <= 400; ++ r) { int ost = i % r; dp[i] += act[r][ost]; dp[i] %= mod; } ans += dp[i]; ans %= mod; if(d[i] && d[i] <= 400) { act[d[i]][i % d[i]] += dp[i]; act[d[i]][i % d[i]] %= mod; } for (auto &[prez, j]: rem[i]) { act[prez][j % prez] -= dp[j]; if(act[prez][j % prez] < 0)act[prez][j % prez] += 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...