제출 #108417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108417		nxteru	Boat (APIO16_boat)	C++14	100 / 100	762 ms	12492 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 1000000007
#define PB push_back
ll n,a[505],b[505],dp[1005][505],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++){
			ll *x=r[j],*y=dp[j],*z=s[j];
			if(j>a[i]){
				y[i]=p;
				ans=(ans+p*z[x[i]]%M)%M;
			}
			for(int k=0;k<i;k++)p=(p+y[k]*z[x[k]-x[i]]%M)%M;
		}
	}
	printf("%lld\n",ans);
}

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<cm.size();j++){
               ~^~~~~~~~~~
boat.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<cm.size();i++){
              ~^~~~~~~~~~
boat.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
boat.cpp:13: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