제출 #1111529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111529		jmuzhen	Trains (BOI24_trains)	C++17	21 / 100	2069 ms	8176 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long

struct St {
	int d, x, end;
};
int n;
vector<St> stations;
vector<int> tt;

const int MOD = 1e9 + 7;

int ans = 0;

#define DEBUG false

// returns the number of diff routes starting at src.
int dp(int src) {
	if (DEBUG) cout << "dp:" << src << endl;
	
	if (tt[src] != -1) return tt[src];
	auto& st = stations[src]; int d = st.d, end = st.end;
	if (DEBUG) cout << d << " " << end << endl;
	
	// simple case: if d == 0 then we must stop
	if (d == 0) {
		return 1;
	}
	
	// we can either stop here (ans++)
	// or we can take the train (to src + d, src + ..., <= end)
	
	int value = 0;
	// easier case: stop here
	value += 1;
	
	{ // case 2
		int e = src + d;
		while (e <= end) {
			if (DEBUG) cout << src << " wl: " << e << " <= " << end << endl;
			value += dp(e);
			
			e += d;
		}
	}
	
	value %= MOD;
	tt[src] = value;
	if (DEBUG) cout << "dp:" << src << " = " << value << endl;
	
	return value;
}


signed main() {
	cin >> n;
	stations.resize(n+1);
	tt.resize(n+1, -1);
	for (int i = 1; i <= n; i++) {
		int d, x; cin >> d >> x;
		long long end = min((long long)n, (long long)i + d * x);
		stations[i] = {d, x, (int)end};
	}
	
	ans = dp(1);
	cout << ans << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29