Submission #44207

#	Time	Username	Problem	Language	Result	Execution time	Memory
44207		faustaadp	Boat (APIO16_boat)	C++17	0 / 100	1319 ms	521392 KiB

boat

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,a[550],b[550],j,k,has,p[1010101],mo=1000000007;
int main()
{
	//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
	}
	for(i=n;i>=1;i--)
	{
		vector<ll> v;
		for(j=a[i];j<=b[i];j++)
		{
			ll tem=1;
			for(k=i+1;k<=n;k++)
			{
				if(j>=b[k])
					continue;
				tem+=p[max(0LL,j-a[k]+1)];
				tem%=mo;
			}
			v.pb(tem);
			has+=tem;
			has%=mo;
		}
		p[b[i]-a[i]+1]=0;
		for(j=b[i]-a[i];j>=0;j--)
			p[j]=(p[j+1]+v[j])%mo;
	}
	cout<<has<<"\n";
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42