제출 #99945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99945		TadijaSebez	Boat (APIO16_boat)	C++11	100 / 100	1339 ms	1532 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=505;
const int M=2*N;
const int K=1000050;
const int mod=1e9+7;
int mul(int x, int y){ return (ll)x*y%mod;}
int add(int x, int y){ x+=y;return x>=mod?x-mod:x;}
int sub(int x, int y){ x-=y;return x<0?x+mod:x;}
int pow(int x, int k){ int ans=1;for(;k;k>>=1,x=mul(x,x)) if(k&1) ans=mul(ans,x);return ans;}
int inv(int x){ return pow(x,mod-2);}
int F[K],I[K];
int binom(int n, int k){ return n<k?0:mul(F[n],mul(I[k],I[n-k]));}
int dp[N],tmp[N][N],l[N],r[N];
void calc()
{
	F[0]=1;for(int i=1;i<K;i++) F[i]=mul(F[i-1],i);
	I[K-1]=inv(F[K-1]);for(int i=K-2;~i;i--) I[i]=mul(I[i+1],i+1);
}
int bc[N];
int main()
{
	//calc();
	int n;
	scanf("%i",&n);
	vector<int> all;
	for(int i=1;i<=n;i++)
	{
		scanf("%i %i",&l[i],&r[i]);
		all.pb(l[i]);
		all.pb(r[i]+1);
	}
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	dp[0]=1;
	for(int t=1;t<all.size();t++)
	{
		int L=all[t]-all[t-1];
		bc[0]=1;
		for(int i=1;i<=n;i++) bc[i]=mul(bc[i-1],mul(L-i+1,inv(i)));
		for(int i=1;i<=n;i++) dp[i]=add(dp[i],dp[i-1]);
		for(int j=1;j<=n;j++)
		{
			for(int i=j;i<=n;i++)
			{
				if(all[t-1]<=r[i] && all[t-1]>=l[i]) tmp[i][j]=j==1?dp[i-1]:tmp[i-1][j-1];
				else tmp[i][j]=0;
			}
			if(j==1) for(int i=n;i>=1;i--) dp[i]=sub(dp[i],dp[i-1]);
			for(int i=j;i<=n;i++) dp[i]=add(dp[i],mul(tmp[i][j],bc[j]));
			for(int i=j;i<=n;i++) tmp[i][j]=add(tmp[i][j],tmp[i-1][j]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=add(ans,dp[i]);
	printf("%i\n",ans);
	return 0;
}

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

boat.cpp: In function 'int main()':
boat.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int t=1;t<all.size();t++)
              ~^~~~~~~~~~~
boat.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
boat.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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