Submission #1125558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125558		amarjeetkhan	Trains (BOI24_trains)	C++20	100 / 100	696 ms	257192 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define ss second
#define pb push_back
#define mod 1000000007
#define N 100005
#define INF 1000000000000000005
#define pu push
#define ff first
#define pint pair<int,int>

using namespace std;

int n,go[N][325];
pint arr[N];

inline int add(int a,int b)
{
	a=a%mod;
	b=b%mod;
	a+=b;
	a%=mod;
	return a;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>arr[i].ff>>arr[i].ss;
	}
	int ans[n],sum=0;
	memset(ans,0,sizeof(ans));
	ans[0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<322;j++)
		{
			ans[i]=add(ans[i],go[i][j]);
		}
		sum=add(sum,ans[i]);
		if(arr[i].ff>320)
		{
			int ind=arr[i].ff+i;
			while(ind<n&&arr[i].ss)
			{
				ans[ind]=add(ans[ind],ans[i]);
				arr[i].ss--;
				ind+=arr[i].ff;
			}
		}
		else
		{
			go[i][arr[i].ff]=add(go[i][arr[i].ff],ans[i]);
			if(i+arr[i].ff*(arr[i].ss+1)<n)
				go[i+arr[i].ff*(arr[i].ss+1)][arr[i].ff]=add(go[i+arr[i].ff*(arr[i].ss+1)][arr[i].ff],mod-ans[i]);
		}
		for(int j=1;j<322;j++)
		{
			if(i+j>=n)
				break;
			go[i+j][j]=add(go[i+j][j],go[i][j]);
		}
	}
	cout<<sum<<endl;
	return 0;
}

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