Submission #994584

#	Time	Username	Problem	Language	Result	Execution time	Memory
994584		PenguinsAreCute	Trains (BOI24_trains)	C++17	100 / 100	297 ms	247768 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SQ = 313;
const int MOD = 1e9 + 7;
main() {
	int n; cin >> n;
	int d[n], x[n]; for(int i=0;i<n;i++) cin>>d[i]>>x[i];
	int dp[n], pre[n][SQ];
	for(int i=n;i--;) {
		dp[i]=1;
		if(d[i]>=SQ) for(int j=1;j<=x[i]&&i+j*d[i]<n;j++) {dp[i]+=dp[i+j*d[i]]; if(dp[i]>=MOD) dp[i]-=MOD;}
		else if(d[i]) {
			if(i+d[i]<n) dp[i]+=pre[i+d[i]][d[i]];
			if(i+d[i]*(x[i]+1)<n) dp[i]-=pre[i+d[i]*(x[i]+1)][d[i]];
			if(dp[i]>=MOD) dp[i]-=MOD;
			if(dp[i]<0) dp[i]+=MOD;
		}
		for(int j=1;j<SQ;j++) {pre[i][j]=dp[i]+(i+j<n?pre[i+j][j]:0); if(pre[i][j]>=MOD) pre[i][j]-=MOD;}
	}
	cout << dp[0];
}

Compilation message (stderr)

Main.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main() {
      | ^~~~

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