Submission #994561

#	Time	Username	Problem	Language	Result	Execution time	Memory
994561		emptypringlescan	Trains (BOI24_trains)	C++17	100 / 100	148 ms	8448 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long buc=316,mod=1000000007;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	pair<long long,long long> arr[n+1];
	for(int i=1; i<=n; i++) cin >> arr[i].first >> arr[i].second;
	long long dp[n+1];
	memset(dp,0,sizeof(dp));
	dp[1]=1;
	long long smol[buc+5][buc+5]; //div, rem
	memset(smol,0,sizeof(smol));
	vector<pair<int,long long> > stop[n+1];
	long long ans=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<buc; j++){
			dp[i]+=smol[j][i%j];
			dp[i]%=mod;
		}
		ans+=dp[i];
		ans%=mod;
		for(auto j:stop[i]){
			smol[j.first][i%j.first]-=j.second;
			smol[j.first][i%j.first]%=mod;
			if(smol[j.first][i%j.first]<0) smol[j.first][i%j.first]+=mod;
		}
		if(arr[i].first==0||arr[i].second==0) continue;
		else if(arr[i].first<buc){
			smol[arr[i].first][i%arr[i].first]+=dp[i];
			smol[arr[i].first][i%arr[i].first]%=mod;
			if(i+arr[i].first*arr[i].second<=n){
				stop[i+arr[i].first*arr[i].second].push_back({arr[i].first,dp[i]});
			}
		}
		else{
			for(int j=1; j<=arr[i].second; j++){
				if(i+j*arr[i].first>n) break;
				dp[i+j*arr[i].first]+=dp[i];
				dp[i+j*arr[i].first]%=mod;
			}
		}
	}
	cout << ans;
}

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