Submission #1276792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276792		huyngodzz	Trains (BOI24_trains)	C++20	100 / 100	332 ms	126412 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define FOR(i ,a ,b) for(int i = a; i <= b; i++)
const int maxN = 1e5 + 999;
const int mod = 1e9 + 7;
int n , d[maxN] , x[maxN];
namespace sub1{
	long long dp[maxN];
	bool check(){
		return (n <= 5000);
	}
	void solve(){
		dp[1] = 1;
		FOR(i, 1, n){
			if(d[i] == 0)continue;
			FOR(j ,1 , x[i]){
				long long  nxt = i + 1LL * j * d[i];
				if(nxt > n)break;
				dp[nxt] = (dp[nxt] + dp[i])%mod;
			}
		}
		long long ans = 0;
		FOR(i, 1, n){
			ans = (ans + dp[i])%mod;
		}
		cout << ans;
	}
}
namespace ac{
	int B;
	void Fixmod(int & x){
		if(x >= mod) x-=mod;
		if(x < 0)x += mod;
	}
	int dp[maxN];
	int cnt[320][maxN];
	void solve(){
		B = sqrt(n);
		dp[1] = 1;
		FOR(i, 1, n){
			FOR(j, 1 , B){
				if(i - j < 1)break;
				cnt[j][i] = (cnt[j][i] + cnt[j][i - j])%mod;
				Fixmod(cnt[j][i]);
		 		dp[i] = (dp[i] + cnt[j][i])%mod;
				Fixmod(dp[i]);
			}
			///update
			if(d[i] > B){
				FOR(j ,1 , x[i]){
					long long  nxt = i + 1LL * j * d[i];
					if(nxt > n)break;
					dp[nxt] = (dp[nxt] + dp[i])%mod;
				}
			}else{
				if(d[i] == 0)continue;
				cnt[d[i]][i] = (cnt[d[i]][i] + dp[i])%mod;
				Fixmod(cnt[d[i]][i]);
				long long  kk  = (i + 1LL* (x[i] + 1)* d[i]);
				if(kk <= n){
					cnt[d[i]][kk] = (cnt[d[i]][kk] - dp[i]);
					Fixmod(cnt[d[i]][kk]);
				}
			}
		}
		int ans =0 ;
		FOR(i, 1, n){
			ans = (ans + dp[i])%mod;
			Fixmod(ans);
		}
		cout << ans;
//		cerr << ans << '\n';

	}
}
void solve(){
	cin >> n ;
	FOR(i, 1 , n){
		cin >> d[i] >> x[i];
	}
//	cout << sqrt(1e5);
	if(sub1::check())return sub1::solve();
	return ac::solve();
}
const string NAME = "task";
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen("train.inp", "r" ,stdin);
//	freopen("train.out", "w" ,stdout);
//	freopen(NAME +"out", "w" , stdout);
	solve();
}

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