Submission #51626

#	Time	Username	Problem	Language	Result	Execution time	Memory
51626		tmwilliamlin168	Boat (APIO16_boat)	C++14	100 / 100	597 ms	8628 KiB

boat

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

#define getchar_unlocked getchar
#define putchar_unlocked putchar
#define ll long long

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(int x) {
	int rev=x, c=0;
	if(!x) {
		putchar_unlocked('0');
		return;
	}
	while(!(rev%10)) {
		++c;
		rev/=10;
	}
	rev=0;
	while(x) {
		rev=rev*10+x%10;
		x/=10;
	}
	while(rev) {
		putchar_unlocked(rev%10+'0');
		rev/=10;
	}
	while(c--)
		putchar_unlocked('0');
}

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() {
	n=in();
	for(int i=0; i<n; ++i) {
		a[i]=in()-1;
		b[i]=in();
		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];
			for(int k=i, n2=0; k; --k) {
				if(pts[j]>a[k-1]&&pts[j]<=b[k-1]) {
					++n2;
					dp[i][j]+=dp[k-1][j-1]*c[j][n2]%M;
				}
			}
			dp[i][j]%=M;
		}
	}
	out(dp[n][pts.size()-1]-1);
}

Compilation message (stderr)

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

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