Submission #23525

#	Time	Username	Problem	Language	Result	Execution time	Memory
23525		ztrong	Boat (APIO16_boat)	C++14	100 / 100	689 ms	10096 KiB

boat

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

#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define REP(i, a) for (int i = 0, _a = a; i < _a; ++i)
#define llint long long
#define sz(x) (x.size())
#define LL(x) (x * 2)
#define RR(x) (x * 2 + 1)
#define fi first
#define se second
#define db(x) cout << #x << " = " << x << endl;
#define BIT(x, i) ((x >> i) & 1)
#define MASK(i) (1ll << i)
#define times clock() * 1.0 / CLOCKS_PER_SEC

void openFile() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifdef Tr___
	freopen("test.inp", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
}

const int maxN = 1e3 + 5;
const int maxM = 1e6 + 5;
const llint INF = 1e9 + 7;

int N;
vector<int> all;
int a[maxN], b[maxN];
llint dp[maxN][maxN], len[maxN], inv[maxN];

void enter() {
	cin >> N;
	FOR(i, 1, N) {
		cin >> a[i] >> b[i];
		all.push_back(a[i]);
		all.push_back(b[i] + 1);
	}
}

inline void add(llint &x, llint y) {
	x = (x + y) % INF;
}

void solve() {
	inv[1] = 1;
	FOR(i, 2, maxN - 1) {
		inv[i] = inv[INF % i] * (INF - INF / i) % INF;
	}

	sort(all.begin(), all.end());
	all.erase(unique(all.begin(), all.end()), all.end());
	FOR(i, 1, N) {
		a[i] = upper_bound(all.begin(), all.end(), a[i]) - all.begin();
		b[i] = upper_bound(all.begin(), all.end(), b[i]) - all.begin();
	}

	FOR(i, 1, all.size() - 1) {
		len[i] = all[i] - all[i - 1];
	}

	FOR(i, 0, all.size() - 1) {
		dp[0][i] = 1;
	}

	llint res = 0;

	FOR(i, 1, N) {
		FOR(j, a[i], b[i]) {
			add(dp[i][j], dp[i - 1][j - 1] * len[j]);
			llint num = 1, choose = len[j] - 1;

			FORD(k, i - 1, 1) if (a[k] <= j && j <= b[k]) {
				++num;
				choose = choose * (len[j] + num - 2) % INF * inv[num] % INF;
				if (choose == 0) break;
				add(dp[i][j], dp[k - 1][j - 1] * choose % INF);
 			}
		}
		dp[i][0] = 1;
		FOR(j, 1, all.size() - 1) {
			add(dp[i][j], dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]);
			add(dp[i][j], INF);
		}
	}

	cout << (dp[N][all.size() - 1] - 1 + INF) % INF << endl;
}

int main() {
	openFile();
	enter();
	solve();
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void solve()':
boat.cpp:70:8: warning: unused variable 'res' [-Wunused-variable]
  llint res = 0;
        ^

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