Submission #1111524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111524		jmuzhen	Trains (BOI24_trains)	C++14	21 / 100	2059 ms	8016 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, bool force_stop) {
	if (DEBUG) cout << "dp:" << src << ", " << force_stop << endl;
	
	// simple case: if force_stop just return 1
	if (force_stop) {
		return 1;
	}
	
	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 also
	if (d == 0) {
		return 1;
	}
	
	// we can either stop here (ans++)
	// or we can take the train (to src + d, src + ..., <= end)
	
	// note that at some dest station e, we MUST STOP at e (i.e. cannot get on)
	// if the train there has the same d AND ends before us
	// this is to prevent double counting of the stations after e
	
	// otherwise, if it ends after us, then we give the choice not to stop at e
	// and instead can take a new train starting there
	// however, this current dp function must then stop at e, allowing e to count
	// the rest of the stations
	
	int value = 0;
	// easier case: stop here
	value += 1;
	
	if (!force_stop) {
		int e = src + d;
		while (e <= end) {
			if (DEBUG) cout << src << " wl: " << e << " <= " << end << endl;
			auto& st2 = stations[e]; int d2 = st2.d, end2 = st2.end;
			if (d2 != d) {
				// easier case
				value += dp(e, false);
				if (DEBUG) {
					cout << "case1 " << src << "->" << e << " , newV=" << value << endl;
				}
			}
			else {
				if (end2 <= end) {
					// force stop
					//value += dp(e, true);
					value += dp(e, false);
					if (DEBUG) {
						cout << "case2.1 " << src << "->" << e << endl;
					}
				}
				else {
					// we don't force stop, but immediately terminate while loop
					value += dp(e, false);
					if (DEBUG) {
						cout << "case2.2 " << src << "->" << e << endl;
					}
					//break;
				}
			}
			
			e += d;
		}	
	}
	
	value %= MOD;
	tt[src] = value;
	if (DEBUG) cout << "dp:" << src << ", " << force_stop << " = " << 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, false);
	cout << ans << endl;
}

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