제출 #1059338

#제출 시각아이디문제언어결과실행 시간메모리
1059338ten_xdTrains (BOI24_trains)C++17
100 / 100
231 ms126992 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; #define rep(a,b) for(int a = 0; a < (b); ++a) #define all(t) t.begin(), t.end() #define pb push_back const int N = 1e5+5, INF = 2e9+54321, mod = 1e9+7, K = 317; const ll INF_L = (ll)2e18+54321; int n, wyn; int D[N], X[N], dp[N], S[K][N]; void solve() { cin >> n; rep(i,n) cin >> D[i] >> X[i]; wyn = 0, dp[0] = 1; rep(i,n) { for(int j = 1; j < K; ++j) if(i-j >= 0) S[j][i] = (S[j][i]+S[j][i-j]) % mod; for(int j = 1; j < K; ++j) dp[i] = (dp[i]+S[j][i]) % mod; wyn = (wyn+dp[i]) % mod; if(D[i] >= K) { for(int j = 1; j <= X[i] and (ll)i+(ll)j*D[i] < (ll)n; ++j) { dp[i+j*D[i]] = (dp[i+j*D[i]]+dp[i]) % mod; } } else { S[D[i]][i] = (S[D[i]][i]+dp[i]) % mod; S[D[i]][min((ll)n,(ll)i+(ll)(X[i]+1)*D[i])] = (S[D[i]][min((ll)n,(ll)i+(ll)(X[i]+1)*D[i])]-dp[i]+mod) % mod; } /*cout << '\n' << '\n'; cout << "I: " << i << " DP: " << dp[i] << '\n'; for(int j = 0; j <= 10; ++j) cout << "J: " << j << " S: " << S[j][i] << '\n'; cout << '\n' << '\n';*/ } cout << wyn << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T = 1; //cin >> T; while(T--) solve(); 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...