Submission #51602

#	Time	Username	Problem	Language	Result	Execution time	Memory
51602		tmwilliamlin168	Boat (APIO16_boat)	C++14	0 / 100	101 ms	8184 KiB

boat

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

#define ll long long

const int mxN=500, M=1e9+7;
int n, a[mxN], b[mxN];
ll dp[mxN+1][2*mxN], c[2*mxN][mxN+1];
vector<int> pts;

inline ll modI(ll a, ll m) {
	return a<=1?a:(1-modI(m%a, a)*m)/a+m;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
//	cout << modI(2, M) << endl;
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> a[i] >> b[i], --a[i];
		pts.push_back(a[i]);
		pts.push_back(b[i]);
	}
	sort(pts.begin(), pts.end());
	pts.resize(unique(pts.begin(), pts.end())-pts.begin());
	for(int i=1; i<pts.size(); ++i) {
		c[i][1]=pts[i]-pts[i-1];
		for(int j=2; j<=n; ++j)
			c[i][j]=c[i][j-1]*(pts[i]-pts[i-1]+j-1)%M*modI(j, M)%M;
	}
	for(int i=0; i<pts.size(); ++i)
		dp[0][i]=1;
	for(int i=1; i<=n; ++i) {
		dp[i][0]=1;
		for(int j=1; j<pts.size(); ++j) {
			dp[i][j]=dp[i][j-1];
			if(pts[j]<=a[i-1]||pts[j]>b[i-1])
				continue;
			for(int k=0; k<i; ++k)
				dp[i][j]+=dp[k][j-1]*c[j][i-k]%M;//, cout << c[j][i-k] << " ";
//			cout << endl;
			dp[i][j]%=M;
//			cout << i << " " << j << " " << dp[i][j] << endl;
		}
	}
	cout << dp[n][pts.size()-1]-1;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<pts.size(); ++i) {
               ~^~~~~~~~~~~
boat.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<pts.size(); ++i)
               ~^~~~~~~~~~~
boat.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1; j<pts.size(); ++j) {
                ~^~~~~~~~~~~

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