Submission #1361922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361922		bozz	Trains (BOI24_trains)	C++20	21 / 100	2095 ms	1092 KiB

Main

#include<bits/stdc++.h>
using namespace std;
constexpr long long MOD=1e9+7;
vector<long long>rs;
//vector<vector<int>>ad;
int main(){
	int N;
	cin>>N;
	rs.resize(N);
	//ad.resize(N);

	long long d,x;
	rs[0]=1;
	long long ris=0;
	for(int i=0;i<N;i++){
		cin>>d>>x;
		//cout<<"i: "<<i<<" - "<<rs[i]<<endl;
		ris=(ris+rs[i])%MOD;
		if(d==0 or rs[i]==0)continue;
		for(int t=1;t<=x;t++){
			int ns=i+t*d;
			if(ns>=N)break;
			//ad[i].push_back(i+t*d);
			rs[ns]=(rs[ns]+rs[i])%MOD;
		}
		
		//cout<<"!"<<endl;
		
	}
	cout<<ris<<endl;
}

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