Submission #679863

#	Time	Username	Problem	Language	Result	Execution time	Memory
679863		buidangnguyen05	Boat (APIO16_boat)	C++14	9 / 100	124 ms	6360 KiB

boat

//source: 

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

typedef long long ll;

const int N = 510, mod = 1e9 + 7;

int pw(int x, int y) {
	if (!y) return 1;
	int mid = pw(x, y / 2);
	if (y & 1) return 1LL * mid * mid % mod * x % mod;
	return 1LL * mid * mid % mod;
}

int a[N], b[N], C[2 * N][N], f[N][2 * N], pref[N][2 * N];

void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	if (fopen("APIO16_boat.inp", "r")) {
		freopen("APIO16_boat.inp", "r", stdin);
		freopen("APIO16_boat.out", "w", stdout);
	}

	#ifdef LOCAL_MACHINE 
		if (fopen("task.inp", "r")) {
			freopen("task.inp", "r", stdin);
			freopen("task.out", "w", stdout);
		}
	#endif
	
	int n; cin >> n;
	vector<int> points;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
		points.push_back(a[i]); points.push_back(b[i] + 1);
	}

	sort(points.begin(), points.end());
	points.resize(unique(points.begin(), points.end()) - points.begin());

	vector<pair<int, int>> lines; lines.emplace_back(-1, -1);
	for (int i = 0; i + 1 < points.size(); ++i) {
		lines.emplace_back(points[i], points[i + 1] - 1);
		int len = points[i + 1] - points[i];
		C[i + 1][0] = 1;
		for (int j = 1; j <= n; ++j) C[i + 1][j] = 1LL * C[i + 1][j - 1] * (len - j + 1) % mod * pw(j, mod - 2) % mod;
	}

	int t = lines.size();
	for (int i = 0; i < t; ++i) pref[0][i] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j < t; ++j) {
			int cnt = 1; f[i][j] = f[i - 1][j];
			if (lines[j].first >= a[i] && lines[j].first <= b[i]) for (int k = i - 1; ~k; --k) {
				add(f[i][j], 1LL * pref[k][j - 1] * C[j][cnt] % mod);
				if (lines[j].first >= a[k] && lines[j].second <= b[k]) ++cnt;
				else break;
			}
		}
		f[i][0] = pref[i][0] = 1;
		for (int j = 1; j < t; ++j) pref[i][j] = (pref[i][j - 1] + f[i][j]) % mod;
	}

	int res = pref[n][t - 1];
	add(res, -1);
	cout << res << "\n";
}

// ඞඞඞඞඞ you sus

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:50:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0; i + 1 < points.size(); ++i) {
      |                  ~~~~~~^~~~~~~~~~~~~~~
boat.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   freopen("APIO16_boat.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:29:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   freopen("APIO16_boat.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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