Submission #734529

#	Time	Username	Problem	Language	Result	Execution time	Memory
734529		vjudge1	Boat (APIO16_boat)	C++14	100 / 100	590 ms	2472 KiB

boat

#include<stdio.h>
#include<algorithm>
#define N 509
#define M 1009
#define mod 1000000007
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,a[N],b[N],lsh[M],f[N][M],inv[N],ans;
inline long long ksm(long long a,int b)
{
	long long ans=1;
	for(;b;b>>=1,a*=a,a%=mod)if(b&1)ans*=a,ans%=mod;
	return ans;
}
main()
{
	read(n);
	for(int i=1;i<=n;inv[i]=ksm(i,mod-2),++i)
		read(a[i]),read(b[i]),lsh[m++]=a[i],lsh[m++]=b[i]+1;
	lsh[m++]=0;lsh[m++]=1000000001;
	sort(lsh,lsh+m);m=unique(lsh,lsh+m)-lsh;--m;
	for(int i=0;i<m;f[0][i++]=1);
	for(int i=1;i<=n;++i)
	{
		for(int l=lower_bound(lsh,lsh+m,a[i])-lsh,r=upper_bound(lsh,lsh+m,b[i])-lsh
			;l<r;++l)
		{
			for(int j=i-1,k=lsh[l+1]-lsh[l],cnt=1;j>=0;--j)
			{
				f[i][l]=(f[i][l]+(long long)(k)*f[j][l-1])%mod;
				if(a[j]<=lsh[l]&&lsh[l]<=b[j])++cnt,
					k=k*(long long)(lsh[l+1]-lsh[l]+cnt-1)%mod*inv[cnt]%mod;
			}
		}
		for(int j=1;j<m;++j)f[i][j]+=f[i][j-1]-mod,f[i][j]>>31&&(f[i][j]+=mod);
		ans+=f[i][m-1]-mod,ans>>31&&(ans+=mod);
	}
	printf("%d",ans);
}

Compilation message (stderr)

boat.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main()
      | ^~~~

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