제출 #1345743

#제출 시각아이디문제언어결과실행 시간메모리
1345743islam_2010Trains (BOI24_trains)C++17
8 / 100
218 ms1704 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int sz = 2e5+5;

int dp[sz];

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

    int n;
	cin >> n;
	vector<array<int, 2>> v;
	for(int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		
		v.push_back({a, b});
	}dp[1] = 1;
	for(int i = 1; i <= n; i++){
		if(v[i-1][0] == 0 || v[i-1][0] > 1e5) continue;
		for(int j = 1; j <= v[i-1][1]; j++){
			if(i + j*v[i-1][0] > n) break;
			dp[i + j*v[i-1][0]] += dp[i];
		}
	}int s = 0;
	for(int i = 1; i <= n; i++){
		s += dp[i];
	}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...