Submission #1314382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314382		boclobanchat	Boat (APIO16_boat)	C++20	100 / 100	1317 ms	16492 KiB

boat

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
const long long mod=1e9+7;
long long dp[MAXN][MAXN],pre[MAXN][MAXN],sum[MAXN],val[MAXN],L[MAXN],R[MAXN],inv[MAXN];
long long poww(long long n,long long m)
{
	long long res=n,ans=1;
	while(m)
	{
		if(m&1) ans=ans*res%mod;
		res=res*res%mod,m/=2;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		cin>>L[i]>>R[i];
		val[++cnt]=L[i],val[++cnt]=R[i]+1;
	}
	for(int i=1;i<=cnt;i++) inv[i]=poww(i,mod-2);
	sort(val+1,val+cnt+1);
	dp[0][1]=1;
	for(int i=1;i<=n;i++)
	{
		int l=lower_bound(val+1,val+cnt+1,L[i])-val;
		int r=lower_bound(val+1,val+cnt+1,R[i]+1)-val-1;
		for(int j=0;j<cnt;j++)
		{
			sum[j]=0;
			for(int k=1;k<=n;k++) pre[j][k]=dp[j][k],sum[j]=(sum[j]+pre[j][k])%mod;
			if(j) sum[j]=(sum[j]+sum[j-1])%mod;
		}
		for(int j=l;j<=r;j++) for(int k=1;k<=n;k++) dp[j][k]=(dp[j][k]+sum[j-1]*(val[j+1]-val[j])*(k==1)+pre[j][k-1]*max(0LL,val[j+1]-val[j]-k+1)%mod*inv[k])%mod;
	}
	long long ans=0;
	for(int j=0;j<cnt;j++) for(int k=1;k<=n;k++) ans=(ans+dp[j][k])%mod;
	cout<<(ans-1+mod)%mod;
}

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