oj.uz

Submission #1052928

# Submission time Handle Problem Language Result Execution time Memory
1052928 2024-08-11T06:09:11 Z vjudge1 Trains (BOI24_trains) C++17
34 / 100
 29 ms 3444 KB 
#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]*2)%mod + (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;
		}
	}
	// 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:42:7: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   42 |  bool b=1;
      |       ^

Subtask #1
0 / 8.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Output is correct
2 Correct 13 ms 2824 KB Output is correct
3 Correct 28 ms 3428 KB Output is correct
4 Correct 23 ms 3156 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 3 ms 2500 KB Output is correct
8 Correct 29 ms 3444 KB Output is correct

Subtask #5
0 / 29.0

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