Submission #145470

#	Time	Username	Problem	Language	Result	Execution time	Memory
145470		arnold518	Boat (APIO16_boat)	C++14	0 / 100	48 ms	8316 KiB

boat

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;
const ll MOD = 1e9+7;

int N, A[MAXN+10], B[MAXN+10];
vector<int> comp;
ll dp[MAXN+10][MAXN*2+10], psum[MAXN+10][MAXN*2+10], cnt[MAXN*2+10], val[MAXN*2+10];

int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }

ll mypow(ll x, ll y)
{
	if(y==0) return 1;
	if(y%2) return mypow(x, y-1)*x%MOD;
	ll ret=mypow(x, y/2);
	return ret*ret%MOD;
}	
ll inv(ll x) { return mypow(x, MOD-2); }

ll comb(ll n, ll r)
{
	ll i, j;
	r=min(r, n-r);
	ll ret=1;
	for(i=1; i<=r; i++) ret=ret*inv(i)%MOD*(n-i+1)%MOD;
	return ret;
}
ll f(ll i, ll j) { return (comb(i+j-1, i)+MOD-1)%MOD; }

int main()
{
	int i, j;
	
	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%d%d", &A[i], &B[i]), B[i]++, comp.push_back(A[i]), comp.push_back(B[i]);
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());

	dp[0][0]=1;
	for(j=0; j<comp.size(); j++) psum[0][j]=1;
	for(i=1; i<=N; i++)
	{
		for(j=0; j<comp.size(); j++)
		{
			if(!(getcomp(A[i])<=j && j<getcomp(B[i]))) { dp[i][j]=dp[i-1][j]; continue; }
			cnt[j]++;
			if(cnt[j]==1)
			{
				val[j]=psum[i-1][j-1];
				dp[i][j]+=psum[i-1][j-1]*(comp[j]-comp[j-1])%MOD;
			}
			else
			{
				dp[i][j]+=((psum[i-1][j-1]-val[j])*(comp[j]-comp[j-1])%MOD+val[j]*f(cnt[j], comp[j]-comp[j-1]+1)%MOD)%MOD;
			}
			dp[i][j]%=MOD;
		}
		//for(j=0; j<comp.size(); j++) printf("%lld ", dp[i][j]); printf("\n");
		psum[i][0]=dp[i][0];
		for(j=1; j<comp.size(); j++) psum[i][j]=(dp[i][j]+psum[i][j-1])%MOD;
	}
	printf("%lld", (psum[N][comp.size()-1]+MOD-1)%MOD);
}

Compilation message (stderr)

boat.cpp: In function 'll comb(ll, ll)':
boat.cpp:28:8: warning: unused variable 'j' [-Wunused-variable]
  ll i, j;
        ^
boat.cpp: In function 'int main()':
boat.cpp:46:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(j=0; j<comp.size(); j++) psum[0][j]=1;
           ~^~~~~~~~~~~~
boat.cpp:49:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<comp.size(); j++)
            ~^~~~~~~~~~~~
boat.cpp:66:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1; j<comp.size(); j++) psum[i][j]=(dp[i][j]+psum[i][j-1])%MOD;
            ~^~~~~~~~~~~~
boat.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
boat.cpp:41:79: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d%d", &A[i], &B[i]), B[i]++, comp.push_back(A[i]), comp.push_back(B[i]);
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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