Submission #42613

#	Time	Username	Problem	Language	Result	Execution time	Memory
42613		fefe	Boat (APIO16_boat)	C++14	9 / 100	183 ms	15336 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[MAX_N][5*MAX_N],sum[MAX_N][5*MAX_N];
    vector<LL> X;
    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;
    	scanf("%lld",&n);
    	for(i=1;i<=n;i++){
    		scanf("%lld %lld",&arr[i].s,&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());
    	t[0][0]=sum[0][0]=1;
    	for(i=1;i<=4*n+1;i++)	sum[0][i]=1;
    	for(i=1;i<=n;i++){
    		S=lower_bound(X.begin(),X.end(),arr[i].s)-X.begin();
    		E=lower_bound(X.begin(),X.end(),arr[i].e)-X.begin();
    		for(j=2*S+1;j<=2*E+1;j++){
    			s=j%2?X[j/2]:X[j/2-1]+1;
    			e=j%2?X[j/2]:X[j/2]-1;
    			if(s>e)	continue;
    			cnt=1;
    			x=1;
    			t[i][j]=(sum[i-1][j-1]*(e-s+1))%MOD;
    			if(e==s)	continue;
    			for(k=i-1;k>=1;k--){
    				if(arr[k].s>s || arr[k].e<e)	continue;
    				cnt++;
    				x*=(e-s-1+cnt);x%=MOD;x*=inv[cnt];x%=MOD;
    				t[i][j]=(t[i][j]+sum[k-1][j-1]*x)%MOD;				
    			}
    		}
    		sum[i][0]=sum[i-1][0];
    		for(j=1;j<=4*n+1;j++){
    			sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+t[i][j]+MOD)%MOD;
    		}
    	}
    	printf("%lld\n",(sum[n][4*n+1]-1+MOD)%MOD);
    	return 0;
    }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:23:21: warning: unused variable 'y' [-Wunused-variable]
      LL i,j,k,s,e,x,y,S,E,cnt;
                     ^
boat.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%lld",&n);
                      ^
boat.cpp:26:45: 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