제출 #1233613

#제출 시각아이디문제언어결과실행 시간메모리
1233613AriadnaTrains (BOI24_trains)C++20
0 / 100
17 ms2120 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int mod = 1e9+7, N = 1e5; ll dp[N]; int main() { int n; cin >> n; vector<int> d(n), x(n); for (int i = 0; i < n; ++i) cin >> d[i] >> x[i]; vector<int> final(n); vector<vector<int>> ends(n); for (int i = 0; i < n; ++i) { final[i] = min(n-1, i+d[i]*x[i]); ends[final[i]].push_back(i); } ll sum = dp[0] = 1; for (int i = 1; i < n; ++i) { dp[i] = sum; sum += dp[i]; for (int a: ends[i]) sum -= dp[a]; sum %= mod; } ll tot = 0; for (int i = 0; i < n; ++i) { tot += dp[i]; tot%=mod; } cout << tot << 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...