Submission #1125549

#TimeUsernameProblemLanguageResultExecution timeMemory
1125549amarjeetkhanTrains (BOI24_trains)C++20
0 / 100
10 ms8516 KiB
#include <bits/stdc++.h>
#define ss second
#define pb push_back
#define mod 998244353
#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];

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]+=go[i][j];
		}
		sum+=ans[i];
		if(arr[i].ff>320)
		{
			int ind=arr[i].ff+1;
			while(ind<n&&arr[i].ss)
			{
				ans[ind]+=ans[i];
				arr[i].ss--;
			}
		}
		else
		{
			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]-=ans[i];
		}
		for(int j=1;j<322;j++)
		{
			if(i+j>=n)
				break;
			go[i+j][j]+=go[i][j];
		}
	}
	cout<<sum<<endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...