Submission #1250723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250723		mingga	Trains (BOI24_trains)	C++20	34 / 100	113 ms	7372 KiB

Main

// Author: caption_mingle
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 1e5 + 7;
const int B = 330;
int n, a[N], x[N], d[B][B], dp[N];

vector<pair<int, int>> ev[N];

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

int mul(int x, int y) {
	return (1ll * x * y) % mod;
}


signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> x[i];
	}
	dp[1] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j < B; j++) {
			dp[i] = add(dp[i], d[j][i % j]);
		}
		for(auto [pre, gap] : ev[i]) {
			d[gap][pre % gap] = add(d[gap][pre % gap], -dp[pre]);
		}
		int cur_gap = a[i], num_stat = x[i];
		if(cur_gap == 0) continue;
		int fir_stat = i + cur_gap;
		int lst_stat = i + cur_gap * min(num_stat, (n - i) / cur_gap);
		if(cur_gap >= B) {
			for(int j = fir_stat; j <= lst_stat; j += cur_gap) {
				dp[j] = add(dp[j], dp[i]);
			}
		} else {
			d[cur_gap][i % cur_gap] = add(d[cur_gap][i % cur_gap], dp[i]);
			ev[lst_stat].pb({i, cur_gap});
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		ans = add(ans, dp[i]);
	}
	cout << ans << ln;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:38:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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