Submission #200580

#	Time	Username	Problem	Language	Result	Execution time	Memory
200580		red1108	Boat (APIO16_boat)	C++17	0 / 100	19 ms	12280 KiB

boat

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e16;
const int inf = 2e9;
template<class T>
void pr(T t) {cout << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cout << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cout << endl <<endl;}
 
int in[510][2], n;
vector<int> h;
int cnt[1010];
ll dp[510][1010],mod=1e9+7,ncr[510][510],choice[1010][510],iinv[510],ndr[1010][510];
ll mypow(ll a, ll b){
	ll ret=1;
	while(b){
		if(b&1) ret = ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}
int main(){
	fastio;
	cin>>n;
	h.eb(0);
	for(int i=1;i<=n;i++){
		cin>>in[i][0]>>in[i][1];in[i][1]++;
		h.eb(in[i][0]);h.eb(in[i][1]);
	}
	ncr[0][0]=1;
	for(int i=1;i<=n;i++){
		ncr[i][0]=1;
		for(int j=1;j<=i;j++) ncr[i][j]=(ncr[i-1][j-1]+ncr[i-1][j])%mod;
	}
	for(int i=1;i<=n;i++) iinv[i]=mypow(i,mod-2);
	sort(h.begin(),h.end());
	h.resize(unique(all(h))-h.begin());
	for(int i=1;i<=n;i++){
		in[i][0]=lower_bound(all(h),in[i][0])-h.begin();
		in[i][1]=lower_bound(all(h),in[i][1])-h.begin();
		for(int j=in[i][0];j<in[i][1];j++) cnt[j]++;
	}
	for(int j=1;j<h.size()-1;j++){
		ll m = h[j+1]-h[j], c = 1;
		ndr[j][0]=1;
		for(int i=1;i<=n;i++){
			if(i>m) break;
			c = c * (m-i+1)%mod * iinv[i]%mod;
			ndr[j][i]=c;
		}
	}
	for(int j=1;j<h.size()-1;j++){
		choice[j][1]=h[j+1]-h[j];
		for(int s=2;s<=cnt[j];s++){
			choice[j][s]=choice[j][s-1];
			for(int i=2;i<=s;i++)
				choice[j][s] = (choice[j][s] + ndr[j][i] * ncr[s-2][i-2] ) %mod;
		}
	}
	ll ans=0;
	for(int i=0;i<=2*n;i++) dp[0][i]=1;
	for(int i=1;i<=n;i++){
		if(i==1){
			for(int j=in[i][0];j<in[i][1];j++) dp[i][j]=dp[i][j-1]+h[j+1]-h[j];
			continue;
		}
		for(int j=in[i][0];j<in[i][1];j++){
			dp[i][j]=dp[i][j-1];
			int num=0;
			for(int k=i;k>=1;k--){
				if(in[k][0]<=j&&j<in[k][1]) num++;
				dp[i][j]=(dp[i][j]+dp[k-1][j-1]*choice[j][num]%mod)%mod;
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans = (ans + dp[i][in[i][1]-1])%mod;
	}
	cout<<ans;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=1;j<h.size()-1;j++){
              ~^~~~~~~~~~~
boat.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=1;j<h.size()-1;j++){
              ~^~~~~~~~~~~

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