Submission #44209

#	Time	Username	Problem	Language	Result	Execution time	Memory
44209		faustaadp	Boat (APIO16_boat)	C++17	9 / 100	2059 ms	524288 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,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];
	}
	vector<ll> v[550],p[550];
	for(i=n;i>=1;i--)
	{
		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[k][max(0LL,j-a[k]+1)];
				tem%=mo;
			}
			v[i].pb(tem);
			p[i].pb(0);
			has+=tem;
			has%=mo;
		}
		p[i].pb(0);
		for(j=b[i]-a[i];j>=0;j--)
			p[i][j]=(p[i][j+1]+v[i][j])%mo;
	}
	cout<<has<<"\n";
}

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