제출 #1026481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026481		mansur	Trains (BOI24_trains)	C++17	100 / 100	806 ms	745688 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 = 1e5 + 1, mod = 1e9 + 7;
const ll inf = 1e18;

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

int n, k = 300;
int d[N], x[N];

void gamicrab() {
	int dp[n + 1];
	k = min(n, k);
	vector<int> val[k][k];
	for (int j = 1; j < k; j++) {
	    for (int s = 0; s < k; s++) {
	    	val[j][s].resize(n / j + 2);
	    }
	}	
	for (int i = n; i >= 1; i--) {
		dp[i] = 1;
		if (d[i]) {
			if (d[i] >= k) {
			 	for (int j = i + d[i], z = 1; j <= n && z <= x[i]; j += d[i], z++) {
			 		dp[i] = sum(dp[i], dp[j]);
			 	}
			}else {
				int p = min(sz(val[d[i]][0]) - 1ll, (i + d[i] * 1ll * x[i]) / d[i] + 1);
				int vl = sum(val[d[i]][i % d[i]][i / d[i] + 1], -val[d[i]][i % d[i]][p]);
				dp[i] = sum(dp[i], vl);
			}
		}
		for (int j = 1; j < k; j++) {
			val[j][i % j][i / j] = sum(val[j][i % j][i / j + 1], dp[i]);
		}
	}
	cout << dp[1];
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> d[i] >> x[i];                                 
	gamicrab();
}                                                      

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

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