Submission #23505

#	Time	Username	Problem	Language	Result	Execution time	Memory
23505		petrpan	Boat (APIO16_boat)	C++14	0 / 100	2000 ms	25856 KiB

boat

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>


using namespace std;

long long n,a[510],b[510],sz,rev[1010],mod=1e9+7,f[1010][1010],al[1010][1010];
vector<int> q;
map<int,long long> cmb[1010];

//fast exponential

long long exp(long long a,long long b)
{
	long long ret=1;
	while (b)
	{
		if (b%2)
			ret*=a,ret%=mod;
		a*=a;
		a%=mod;
		b/=2;
	}
	return ret;
}

long long combi(int i,int j)
{
	//cout << "C " << i << " " << j << "\n";
	if (i>j) return 0;
	if (i==0) return 1;
	if (cmb[i][j]) return cmb[i][j];
	return (((combi(i-1,j)*i)%mod)*rev[j-i+1])%mod;
}


//dp result dp(i,j) number of way to send boat
//from schools 1->i such that last num < q[j]

long long dp(int p,int cur)
{
	//cout << p << " " << cur << "\n";
	if (p==0) return 1;
	if (cur<=1) return 0;
	if (al[p][cur]) return f[p][cur];
	al[p][cur]=1;
	f[p][cur]+=dp(p,cur-1);
	f[p][cur]+=(dp(p-1,cur)-dp(p-1,cur-1))+mod;
	f[p][cur]%=mod;
	if (q[cur-1]>b[p] or q[cur]<=a[p]) return f[p][cur];
	for (int i=p;i>=1;i--)
	{
		int x=q[cur]-q[cur-1];
		f[p][cur]+=(dp(i-1,cur-1)*combi(p-i+1,x+p-i+1-1))%mod;
		f[p][cur]%=mod;
	}
	f[p][cur]%=mod;
	return f[p][cur];
}

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
	{
		cin >> a[i] >> b[i];
		//discretize segments
		q.push_back(a[i]);
		q.push_back(b[i]+1);
	}
	q.push_back(0);
	sort(q.begin(),q.end());
	q.resize(unique(q.begin(),q.end())-q.begin());
	//reverse modulo
	for (int i=1;i<1010;i++)
		rev[i]=exp(i,mod-2);
	sz=q.size()-1;
	cout << dp(n,sz);
}

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