제출 #372828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372828		ogibogi2004	Boat (APIO16_boat)	C++14	100 / 100	816 ms	6636 KiB

boat

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const ll MAXN=1024;
ll dp[MAXN][2*MAXN];
ll l1[2*MAXN],r1[2*MAXN];
ll n;
ll a[MAXN],b[MAXN];
ll a1[MAXN],b1[MAXN];
ll inv[MAXN];
ll fastpow(ll x,ll p)
{
	if(p==0)return 1;
	ll t=fastpow(x,p/2);
	t*=t;t%=mod;
	if(p%2==1)t*=x;
	t%=mod;
	return t;
}
int main()
{
	cin>>n;
	vector<ll>v;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		v.push_back(a[i]);
		v.push_back(b[i]+1);
	}
	sort(v.begin(),v.end());
	int cnt=0;
	for(int i=1;i<v.size();i++)
	{
		if(v[i]==v[i-1])continue;
		cnt++;
		l1[cnt]=v[i-1];
		r1[cnt]=v[i]-1;
	}
	for(int i=0;i<2*MAXN;i++)
	{
		dp[0][i]=1;
	}
	for(int i=1;i<MAXN;i++)inv[i]=fastpow(i,mod-2);
	for(int i=1;i<=cnt;i++)
	{
		ll t=r1[i]-l1[i]+1;
		for(int j=1;j<=n;j++)
		{
			dp[j][i]=dp[j][i-1];
			if(a[j]>r1[i]||b[j]<l1[i])continue;
			ll fnaf=t,c=1;
			for(int k=j-1;k>=0;k--)
			{
				dp[j][i]=dp[j][i]+dp[k][i-1]*fnaf;
				dp[j][i]%=mod;
				if(a[k]<=l1[i]&&b[k]>=r1[i])
				{
					fnaf=fnaf*(t+c);
					fnaf%=mod;
					c++;
					fnaf*=inv[c];
					fnaf%=mod;
				}
			}
		}
	}
	ll ans=0;
	for(ll i=1;i<=n;i++)
	{
		ans+=dp[i][cnt];ans%=mod;
	}
	cout<<ans<<endl;
return 0;
}

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

boat.cpp: In function 'int main()':
boat.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i=1;i<v.size();i++)
      |              ~^~~~~~~~~

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