Submission #994671

#	Time	Username	Problem	Language	Result	Execution time	Memory
994671		hmm789	Trains (BOI24_trains)	C++14	100 / 100	718 ms	131924 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define MOD 1000000007

const int B = 320;
int sm[B][B][B];

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	int d[n], x[n], dp[n];
	for(int i = 0; i < n; i++) cin >> d[i] >> x[i];
	for(int i = n-1; i >= 0; i--) {
		dp[i] = 1;
		if(d[i] == 0) {
		} else if(d[i] < B) {
			int mn = min(i+d[i]*x[i], n-1);
			while(mn % d[i] != i%d[i]) mn--;
			int lblk = i/B, rblk = mn/B;
			if(rblk-lblk < 2) {
				for(int j = 1; j <= x[i]; j++) {
					if(i+j*d[i] >= n) break;
					dp[i] += dp[i+j*d[i]];
					dp[i] %= MOD;
				}
			} else {
				for(int j = lblk+1; j < rblk; j++) {
					dp[i] += sm[d[i]][i%d[i]][j];
					dp[i] %= MOD;
				}
				int st = (lblk+1)*B-1, ed = rblk*B;
				st = st-st%d[i]+i%d[i];
				if(st >= (lblk+1)*B) st -= d[i];
				for(; st > i; st -= d[i]) {
					dp[i] += dp[st];
					dp[i] %= MOD;
				}
				ed = ed-ed%d[i]+i%d[i];
				if(ed < rblk*B) ed += d[i];
				for(; ed <= mn; ed += d[i]) {
					dp[i] += dp[ed];
					dp[i] %= MOD;
				}
			}
		} else {
			for(int j = 1; j <= x[i]; j++) {
				if(i+j*d[i] >= n) break;
				dp[i] += dp[i+j*d[i]];
				dp[i] %= MOD;
			}
		}
		for(int j = 1; j < B; j++) {
			sm[j][i%j][i/B] += dp[i];
			sm[j][i%j][i/B] %= MOD;
		}
	}
	cout << dp[0];
}

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