Submission #1052932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1052932	2024-08-11T06:16:47 Z	vjudge1	Trains (BOI24_trains)	C++17	50 / 100	34 ms	3576 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=1e5+5;
int const mod=1e9+7;

int dp[N],suf[N],d[N],x[N];
int n;
void solve(){
	dp[n]=1;
	suf[n]=1;
	for(int i=n-1;i>=1;i--){
		dp[i]=1;
		if(d[i]==0){
			suf[i]=1;
			continue;
		}
		for(int j=i+d[i];j<=n;j+=d[i]){
			if(d[j]==d[i]){
				dp[i]=(dp[i]+suf[j])%mod;
				break;
			}
			dp[i]=(dp[i]+dp[j])%mod;
		}
		suf[i]=(dp[i] + (mod-1))%mod;
		for(int j=i+(d[i]*(x[i]+1)); j<=n;j++){
			if(d[i]==d[j]){
				dp[i]=((dp[i]-suf[j])+mod)%mod;
				break;
			}
			dp[i]=((dp[i]-dp[j])+mod)%mod;
		}
		suf[i]=(dp[i]+suf[i])%mod;
	}
	// for (int i = 1; i <=n; ++i)
	// 	cout<<dp[i]<<' '<<suf[i]<<endl;

	// for(int i=1;i<=n;i++)
	// 	cout<<dp[i]<<endl;
	cout<<dp[1]<<endl;
}

signed main(){
	cin>>n;
	bool b=1;
	for (int i = 1; i <=n; ++i){
		cin>>d[i]>>x[i];
		if(d[i]!=1)
			b=0;
	}
	solve();
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:46:7: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   46 |  bool b=1;
      |       ^

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Incorrect	0 ms	2396 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #2

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Incorrect	0 ms	2396 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #3

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	2 ms	2396 KB	Output is correct
3	Correct	1 ms	2468 KB	Output is correct
4	Correct	2 ms	2396 KB	Output is correct
5	Correct	11 ms	3188 KB	Output is correct
6	Correct	24 ms	3576 KB	Output is correct
7	Correct	22 ms	3444 KB	Output is correct
8	Correct	1 ms	2408 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	0 ms	2396 KB	Output is correct
11	Correct	3 ms	2652 KB	Output is correct
12	Correct	28 ms	3440 KB	Output is correct
13	Correct	0 ms	2396 KB	Output is correct
14	Correct	3 ms	2652 KB	Output is correct
15	Correct	34 ms	3420 KB	Output is correct

Subtask #4

34.0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	2820 KB	Output is correct
2	Correct	13 ms	2760 KB	Output is correct
3	Correct	34 ms	3412 KB	Output is correct
4	Correct	24 ms	3164 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	5 ms	2652 KB	Output is correct
8	Correct	29 ms	3436 KB	Output is correct

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Incorrect	0 ms	2396 KB	Output isn't correct
7	Halted	0 ms	0 KB	-