Submission #1200058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200058		WH8	Trains (BOI24_trains)	C++20	100 / 100	189 ms	8668 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define f first
#define s second
#define pll pair<int,int>
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
const int bk=350;
const int lm=1000000007;
int way[100005];
vector<vector<int>> mod(bk+10);
vector<vector<tuple<int,int,int>>> rm(100005);
vector<pll> v(100005);
signed main(){
	int n;cin>>n;
	for(int i=1;i<=bk;i++){
		mod[i].resize(i);
	}
	for(int i=0;i<n;i++){
		cin>>v[i].f>>v[i].s;
	}
	way[0]=1;
	for(int i=0;i<n;i++){
		int s=v[i].f, t=v[i].s;
		//~ cout<<i<<endl;
		for(int m=1;m<bk;m++){
			//~ printf("m %lld, i mod m %lld, contrib %lld\n", m,i%m, mod[m][i%m]);
			way[i]+=mod[m][i%m];
			way[i]%=lm;
		}
		if(s != 0){
			if(n > bk * s){
				mod[s][i%s]=(mod[s][i%s]+way[i])%lm;
				if(i + t*s < n) rm[i+t*s].push_back({s,i%s,way[i]});
			}
			else{
				for(int j=1;j<=t and i+j*s < n;j++){
					way[i+j*s]=(way[i+j*s]+way[i])%lm;
				}
			}
		}

		for(auto [m, r, rmv]:rm[i]){
			mod[m][r]-=rmv;
			while(mod[m][r]<0)mod[m][r]+=lm;
		}
		//~ for(int j=0;j<n;j++){
			//~ cout<<way[j]<<' ';
		//~ }
		//~ cout<<endl<<endl;
	}
	
	int ans=0;
	for(int i=0;i<n;i++){
		//~ cout<<way[i]<<" ";
		ans+=way[i];
		ans%=lm;
	}
	//~ cout<<endl;
	cout<<ans;
}

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