Submission #124998

#	Time	Username	Problem	Language	Result	Execution time	Memory
124998		Mamnoon_Siam	Boat (APIO16_boat)	C++17	100 / 100	766 ms	2552 KiB

boat

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

using ll = long long;
const int mod = 1e9 + 7;

ll qpow(ll b, ll p) {
	ll ret = 1;
	while(p) {
		if(p & 1) ret = (ret * b) % mod;
		b = (b * b) % mod, p >>= 1;
	} return ret;
}

struct base {
	ll x;
	void fix() {
		if(x < 0 or x >= mod) x %= mod;
		if(x < 0) x += mod;
	}
	base() {x = 0;}
	base(int _x) { x = _x; fix(); }
	base(ll _x) { x = _x; fix(); }
	base operator + (const base &o) const {
		base ret;
		ret.x = x + o.x;
		if(ret.x >= mod) {
			ret.x -= mod;
		}
		return ret;
	}
	base operator * (const base &o) const { return base(x * o.x); }
	base operator / (const base &o) const {
		return base(x * qpow(o.x, mod - 2)); }
	void operator += (const base &o) { (*this) = (*this) + o; }
	void operator *= (const base &o) { (*this) = (*this) * o; }
};

const int maxn = 505;

int n;
int a[maxn], b[maxn];

int N_rng;
int l[maxn << 1], r[maxn << 1];

base inv[maxn];
base dp[maxn];
base RngC[maxn];
base C[maxn][maxn];
base g[maxn];

int main(int argc, char const *argv[])
{
	scanf("%d", &n);
	vector<int> tmp;
	for(int i = 1; i <= n; i++) {
		scanf("%d %d", &a[i], &b[i]);
		a[i]--;
		tmp.emplace_back(a[i]);
		tmp.emplace_back(b[i]);
	}

	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());

	for(int i = 1; i < tmp.size(); i++) {
		N_rng++;
		l[N_rng] = tmp[i - 1];
		r[N_rng] = tmp[i];
	}

	inv[0] = 1;
	for(int i = 1; i <= n; i++) {
		inv[i] = base(1) / i;
	}
	
	for(int i = 0; i <= n; i++) {
		C[i][0] = 1;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= i; j++) {
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
		}
	}
	
	dp[0] = 1;
	for(int rng = 1; rng <= N_rng; rng++) {
		RngC[0] = 1;
		for(int i = 1, sz = r[rng] - l[rng]; i <= n; i++, sz--) {
			RngC[i] = sz < 1 ? 0 : RngC[i - 1] * inv[i] * sz;
		}
		for(int k = 1; (g[k].x = 0) or k <= n; k++) {
			for(int i = 1; i <= k; i++) {
				g[k] += C[k - 1][i - 1] * RngC[i];
			}
		}
		for(int i = n; i >= 1; i--) {
			if(a[i] <= l[rng] and r[rng] <= b[i]) {
				int cnt = 0;
				for(int k = i; k >= 1; k--) {
					if(a[k] <= l[rng] and r[rng] <= b[k]) {
						cnt++;
					}
					dp[i] += dp[k - 1] * g[cnt];
				}
			}
		}
	}

	base ans = 0;
	for(int i = 1; i <= n; i++) {
		ans += dp[i];
	}
	printf("%d\n", (int)ans.x);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main(int, const char**)':
boat.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < tmp.size(); i++) {
                 ~~^~~~~~~~~~~~
boat.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
boat.cpp:58:8: 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