Submission #259048

#	Time	Username	Problem	Language	Result	Execution time	Memory
259048		ChrisT	Boat (APIO16_boat)	C++17	100 / 100	1992 ms	11640 KiB

boat

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int MN = 505, LOG = 18, MOD = 1e9 + 7;
int dp[MN][MN<<1],pre[MN<<1][MN][2],a[MN],b[MN];
int ch[MN][MN], ch2[MN<<1][MN][2], iv[MN<<1];
int inv (int base) {
	int res = 1, exp = MOD - 2;
	while (exp) {
		if (exp&1) res = (ll)res * base % MOD;
		base = (ll)base * base % MOD;
		exp>>=1;
	}
	return res;
}
int choose (int n, int k) {
	assert(n >= 0 && k >= 0);
	int res = 1;
	for (int i = n; i > n-k; i--) res = (ll)res * i % MOD;
	for (int i = 2; i <= k; i++) res = (ll)res * iv[i] % MOD;
	return res;
}
int calc (int j, int x, bool ree) {
	int ret = ch2[j][x-ree][ree];
	for (int zeros = 1; zeros <= x-2; zeros++) ret = (ret + (ll)ch2[j][x-zeros-ree][ree] * ch[x-2][zeros]) % MOD;
	return ret;
}
int main () {
	int n;
	scanf ("%d",&n);
	for (int i = 0; i <= n*2; i++) iv[i] = inv(i);
	for (int i = 0; i <= n; i++) for (int j = 0; j <= i; j++) ch[i][j] = choose(i,j);
	vector<int> xs = {-1};
	for (int i = 1; i <= n; i++) {
		scanf ("%d %d",&a[i],&b[i]);
		xs.push_back(a[i]); xs.push_back(b[i]);
	}
	sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
	int m = xs.size() - 1;
	for (int j = 1; j <= m; j++) {
		ch2[j][0][0] = ch2[j][0][1] = 1;
		for (int i = 1; i <= n; i++) {
			ch2[j][i][0] = (ll)ch2[j][i-1][0] * (xs[j]-xs[j-1]-i+1) % MOD * inv(i) % MOD;
			ch2[j][i][1] = (ll)ch2[j][i-1][1] * (xs[j]-xs[j-1]-i) % MOD * inv(i) % MOD;
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++) {
			pre[j][i][0] = calc(j,i,0);
			pre[j][i][1] = calc(j,i,1);
		}
	}
	for (int j = 0; j <= m; j++) dp[0][j] = 1;
	for (int i = 1; i <= n; i++) {
		//printf ("i %d\n",i);
		for (int j = 0; j <= m; j++){
			if (j) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
			if (xs[j] < a[i] || (j&&b[i] <= xs[j-1])) continue;
			bool ree = a[i]==xs[j]; int cnt = 0;
			for (int k = i; k >= 1; k--) { //everything before k was <= xs[j-1]
				if (a[k] > xs[j] || b[k] <= xs[j-1] || (k!=i&&a[k]==xs[j])) continue;
				++cnt;
				dp[i][j] = (dp[i][j] + (ll)dp[k-1][j-1] * pre[j][cnt][ree]) % MOD;
			}
		}
		for (int j = 0; j <= m; j++) {
			dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
			//printf ("dp[%d][%d] = %d\n",i,j,dp[i][j]);
		}
	}
	printf ("%d\n",(dp[n][m] + MOD - 1) % MOD);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&n);
  ~~~~~~^~~~~~~~~
boat.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d",&a[i],&b[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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