Submission #1033663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033663		vjudge1	Trains (BOI24_trains)	C++17	100 / 100	501 ms	334828 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int mod = 1e9+7;
int n, d[100005], x[100005], S = 320, dp[100005], pfs[100005][325];
vector<int> adj[100005];
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> d[i] >> x[i];
		if(d[i] > S) for (int j = i+d[i]; j <= min(n, i+d[i]*x[i]); j += d[i]) adj[j].push_back(i);
	}
	dp[1] = 1;
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if(i!=1){
			for (int j = 1; j <= S; j++) pfs[i][j] += pfs[max(0ll,i-j)][j], pfs[i][j] %= mod, pfs[i][j]=(pfs[i][j]+mod)%mod;
			for (int j = 1; j <= S; j++) dp[i] += pfs[i][j], dp[i]%=mod;
			for (int j: adj[i]) dp[i] += dp[j], dp[i] %= mod;
		}
		if(d[i] <= S) pfs[i][d[i]] += dp[i], pfs[min(n+2,i+d[i]*(x[i]+1))][d[i]] -= dp[i];
		res += dp[i], res %= mod;
	}
	cout << res;
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen("input.inp","r")){
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	}
	int t = 1;
	// cin >> t;
	while(t--) {
		solve();
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   freopen("input.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen("output.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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