Submission #42615

#	Time	Username	Problem	Language	Result	Execution time	Memory
42615		fefe	Boat (APIO16_boat)	C++14	9 / 100	469 ms	5412 KiB

boat

#include<bits/stdc++.h>
#define MAX_N 505
#define mod 1000000007LL
#define pb push_back
typedef long long LL;
using namespace std;
struct node{
	LL s,e;
}arr[MAX_N];
LL n,ans,inv[3*MAX_N];
LL t[3*MAX_N][MAX_N],sum[3*MAX_N][MAX_N],ss[MAX_N];
vector<LL> X,lst;
LL Pow(LL x,LL y){
	if(y==0)	return 1;
	if(y==1)	return x;
	LL z=pow(x,y/2);
	z*=z;z%=mod;
	if(y%2)	z*=x;
	z%=mod;
	return z;
}
int main(){
	LL i,j,k,s,e,x,y,S,E,cnt,p;
	scanf("%lld",&n);
	for(i=1;i<=n;i++){
		scanf("%lld %lld",&arr[i].s,&arr[i].e);
		arr[i].e++;
		X.pb(arr[i].s);X.pb(arr[i].e);
	}
	for(i=1;i<=1000;i++)	inv[i]=Pow(i,mod-2);
	sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());
	LL sz=X.size();
	for(i=0;i<=n;i++)	sum[0][i]=1;
	for(i=1;i<sz;i++){
		s=X[i-1];
		e=X[i];
		lst.resize(0);
		for(j=1;j<=n;j++){
			if(arr[j].e>=e && arr[j].s<=s)	lst.pb(j);
		}
		p=e-s;
		y=lst.size();
		for(k=0;k<=y;k++){
			for(j=0;j<=y;j++)	t[k][j]=0;
		}
		for(k=0;k<y;k++)	t[1][k]=(p*sum[i-1][lst[k]-1])%mod;
		for(k=2;k<=y;k++){
			ss[0]=(t[k-1][0])%mod;
			for(j=1;j<y;j++)	ss[j]=(ss[j-1]+t[k-1][j]%mod)%mod;
			for(j=k-1;j<y;j++){
				if(k>p)	t[k][j]=0;
				else	t[k][j]=((ss[j-1]*(p-k+1))%mod*inv[k])%mod;
			}
		}
		for(j=0;j<y;j++){
			ss[j]=0;
			for(k=0;k<=y;k++)	ss[j]=(ss[j]+t[k][j])%mod;
		}
		sum[i][0]=1;
		x=0;
		for(j=1;j<=n;j++){
			sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mod)%mod;
			if(x!=y && lst[x]==j){
				sum[i][j]=(sum[i][j]+ss[x])%mod;
				x++;
			}
		}
	}
	printf("%lld\n",(sum[sz-1][n]-1+mod)%mod);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:23:19: warning: unused variable 'S' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt,p;
                   ^
boat.cpp:23:21: warning: unused variable 'E' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt,p;
                     ^
boat.cpp:23:23: warning: unused variable 'cnt' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt,p;
                       ^
boat.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
boat.cpp:26:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&arr[i].s,&arr[i].e);
                                         ^

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