Submission #108411

#	Time	Username	Problem	Language	Result	Execution time	Memory
108411		nxteru	Boat (APIO16_boat)	C++14	100 / 100	1961 ms	12368 KiB

boat

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
using namespace std;
typedef long long ll;
#define M 1000000007
#define PB push_back
ll n,a[505],b[505],dp[505][1005],s[1005][505],f[505],ans,r[1005][505],l[505];
vector<ll>cm;
int main(void){
    scanf("%lld",&n);
    f[1]=1;
    for(int i=2;i<n;i++)f[i]=M-(M/i)*f[M%i]%M;
    for(int i=0;i<n;i++){
		scanf("%lld%lld",a+i,b+i);
		a[i]--;
		cm.PB(a[i]);
		cm.PB(b[i]);
	}
	sort(cm.begin(),cm.end());
	cm.erase(unique(cm.begin(),cm.end()),cm.end());
	for(int i=0;i<n;i++){
		a[i]=lower_bound(cm.begin(),cm.end(),a[i])-cm.begin();
		b[i]=lower_bound(cm.begin(),cm.end(),b[i])-cm.begin();
	}
	for(int i=n-1;i>=0;i--){
		for(int j=1;j<cm.size();j++){
			if(a[i]<j&&j<=b[i])r[j][i]++;
			r[j][i]+=r[j][i+1];
		}
	}
	for(int i=1;i<cm.size();i++){
		ll p=cm[i]-cm[i-1];
		s[i][0]=1;
		for(ll j=1;j<n;j++){
			s[i][j]=s[i][j-1]*(p+j-1LL)%M*f[j]%M;
		}
	}
	for(int i=0;i<n;i++){
		ll p=1;
		for(int j=1;j<=b[i];j++){
			if(j>a[i]){
				dp[i][j]=p;
				ans=(ans+p*s[j][r[j][i]]%M)%M;
			}
			for(int k=0;k<i;k++)p=(p+dp[k][j]*s[j][r[j][k]-r[j][i]]%M)%M;
		}
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<cm.size();j++){
               ~^~~~~~~~~~
boat.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<cm.size();i++){
              ~^~~~~~~~~~
boat.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
boat.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",a+i,b+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

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