Submission #1345763

#TimeUsernameProblemLanguageResultExecution timeMemory
1345763islam_2010Trains (BOI24_trains)C++17
21 / 100
2094 ms2924 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int sz = 2e5+5;
const int mod = 1e9+7;

int dp[sz];


signed main(){
    ios::sync_with_stdio(false);
	cin.tie(nullptr);

    int n;
	cin >> n;
	vector<array<int, 2>> v;
    bool ok = false;
	for(int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		ok |= (a != 1);
		v.push_back({a, b});
	}
    dp[1] = 1;
	for(int i = 1; i <= n; i++){
		if(v[i-1][0] == 0) continue;
        int c = 0;
		for(int j = i + v[i-1][0]; j <= n && c < v[i-1][1]; j+= v[i-1][0]){
			dp[j] = (dp[j] + dp[i]) % mod;
            c++;
            
		}
	}int s = 0;
	for(int i = 1; i <= n; i++){
        // cout << dp[i] << " ";
		s += dp[i];
        s%=mod;
	}cout << s << endl;
}
#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...