제출 #1058239

#제출 시각아이디문제언어결과실행 시간메모리
1058239ZeroCoolTrains (BOI24_trains)C++14
58 / 100
92 ms238932 KiB
#include <bits/stdc++.h> using namespace std; #define ar array #define int long long #define ld long double #define crash assert(69 == 420) const int MOD = 1e9 + 7; const int INF = 1e9; const int N = 1e5 + 20; const int K = 300; const int LOG = 20; int n; int dp[N]; int ans; int sum[K][N]; void upd(int i,int x){ for(int j = 0;j < K;j++){ sum[j][i] = x; if(i + j < n)sum[j][i] += sum[j][i + j], sum[j][i] %= MOD; } } signed main(){ios_base::sync_with_stdio(false);cin.tie(0); cin>>n; int d[n], t[n]; for(int i = 0;i < n;i++)cin>>d[i]>>t[i]; for(int i = n - 1;i >= 0;i--){ dp[i] = 1; if(d[i] == 0){ upd(i, dp[i]); continue; } if(d[i] >= K){ for(int j = 1;j <= t[i] && i + j * d[i] < n;j++)dp[i] += dp[j], dp[i] %= MOD; }else{ int l = i + d[i], r = i + (t[i] + 1) * d[i]; if(l < n)dp[i] += sum[d[i]][l]; if(r < n)dp[i] -= sum[d[i]][r]; dp[i] = (dp[i] % MOD + MOD) % MOD; } upd(i, dp[i]); } // for(int i = 0;i <n;i++)cout<<dp[i]<<" "; //cout<<'\n'; cout<<dp[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...