제출 #1026434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026434		mansur	Trains (BOI24_trains)	C++17	21 / 100	120 ms	98304 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second 
#define f first

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 1e4 + 1, mod = 1e9 + 7;
const ll inf = 1e18;

bool is[N][N];

int sum(int x, int y) {
	x += y;
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
	return x;
}

int n;
vector<int> d, x;

void slv() {
	for (int i = 1; i <= n; i++) {
		if (d[i]) {
			for (int j = 1, p = i + d[i]; j <= x[i] && p <= n; j++, p += d[i]) {
				is[p][i] = 1;
			}
		}
	}
	int dp[n + 1], ans = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = 0;
		for (int j = 1; j < i; j++) {
			if (is[i][j]) {
				dp[i] = sum(dp[i], dp[j]);
			}
		}
		ans = sum(ans, dp[i]);
	}
	cout << ans;
	exit(0);
}

void slave() {
	int dp[n + 1], sf[n + 2];
	sf[n + 1] = 0;
	for (int i = n; i >= 1; i--) {
		dp[i] = 1;
		if (x[i]) {
			int l = i + 1, r = i + x[i];
			dp[i] = sum(dp[i], sum(sf[l], -sf[r + 1]));
		}
		sf[i] = sum(sf[i + 1], dp[i]);
	}
	cout << dp[1];
	exit(0);
}

void solve() {
	cin >> n;
	d.resize(n + 1);
	x.resize(n + 1);
	int ok = 1;
	for (int i = 1; i <= n; i++) {
		cin >> d[i] >> x[i];
		if (d[i] != 1) ok = 0;
	}
	if (n < N) slv();
	if (ok) slave();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
}

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