답안 #1052871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052871	2024-08-11T05:17:55 Z	vjudge1	Trains (BOI24_trains)	C++17	0 / 100	14 ms	4700 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 solve12(){
	dp[n]=1;
	for(int i=n-1;i>=1;i--){
		dp[i]=1;
		if(d[i]==0)
			continue;
		for(int j=i+d[i];j<=min(i+(d[i]*x[i]),n);j+=d[i])
			dp[i]=(dp[i]+dp[j])%mod;
	}
	cout<<dp[1]<<endl;
}
void solve3(){
	dp[n]=1;
	suf[n]=1;
	for(int i=n-1;i>=1;i--){
		dp[i]=(((1+suf[i+1]-suf[i+x[i]+1])%mod)+mod)%mod;
		suf[i]=(dp[i]+suf[i+1])%mod;
	}
	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;
	}
	if(b==0 && n<=10000)
		solve12();
	else if(b)
		solve3();
	// else
	// 	solve4();
	return 0;
}

Subtask #1

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2492 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	0 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Runtime error	2 ms	4700 KB	Execution killed with signal 11
13	Halted	0 ms	0 KB	-

Subtask #2

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2492 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	0 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Runtime error	2 ms	4700 KB	Execution killed with signal 11
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	2 ms	2396 KB	Output is correct
3	Runtime error	3 ms	4700 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #4

0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	14 ms	2652 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2492 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	0 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Runtime error	2 ms	4700 KB	Execution killed with signal 11
13	Halted	0 ms	0 KB	-