oj.uz

Submission #679863

# Submission time Handle Problem Language Result Execution time Memory
679863 2023-01-09T13:08:34 Z buidangnguyen05 Boat (APIO16_boat) C++14
9 / 100
 124 ms 6360 KB 
//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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 6220 KB Output is correct
2 Correct 124 ms 6312 KB Output is correct
3 Correct 118 ms 6300 KB Output is correct
4 Correct 113 ms 6320 KB Output is correct
5 Correct 111 ms 6232 KB Output is correct
6 Correct 113 ms 6216 KB Output is correct
7 Correct 114 ms 6312 KB Output is correct
8 Correct 119 ms 6360 KB Output is correct
9 Correct 111 ms 6216 KB Output is correct
10 Correct 111 ms 6232 KB Output is correct
11 Correct 115 ms 6276 KB Output is correct
12 Correct 118 ms 6264 KB Output is correct
13 Correct 120 ms 6268 KB Output is correct
14 Correct 111 ms 6340 KB Output is correct
15 Correct 118 ms 6228 KB Output is correct
16 Correct 22 ms 4668 KB Output is correct
17 Correct 23 ms 4680 KB Output is correct
18 Correct 23 ms 4664 KB Output is correct
19 Correct 23 ms 4744 KB Output is correct
20 Correct 23 ms 4668 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 6220 KB Output is correct
2 Correct 124 ms 6312 KB Output is correct
3 Correct 118 ms 6300 KB Output is correct
4 Correct 113 ms 6320 KB Output is correct
5 Correct 111 ms 6232 KB Output is correct
6 Correct 113 ms 6216 KB Output is correct
7 Correct 114 ms 6312 KB Output is correct
8 Correct 119 ms 6360 KB Output is correct
9 Correct 111 ms 6216 KB Output is correct
10 Correct 111 ms 6232 KB Output is correct
11 Correct 115 ms 6276 KB Output is correct
12 Correct 118 ms 6264 KB Output is correct
13 Correct 120 ms 6268 KB Output is correct
14 Correct 111 ms 6340 KB Output is correct
15 Correct 118 ms 6228 KB Output is correct
16 Correct 22 ms 4668 KB Output is correct
17 Correct 23 ms 4680 KB Output is correct
18 Correct 23 ms 4664 KB Output is correct
19 Correct 23 ms 4744 KB Output is correct
20 Correct 23 ms 4668 KB Output is correct
21 Incorrect 108 ms 6152 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 6220 KB Output is correct
2 Correct 124 ms 6312 KB Output is correct
3 Correct 118 ms 6300 KB Output is correct
4 Correct 113 ms 6320 KB Output is correct
5 Correct 111 ms 6232 KB Output is correct
6 Correct 113 ms 6216 KB Output is correct
7 Correct 114 ms 6312 KB Output is correct
8 Correct 119 ms 6360 KB Output is correct
9 Correct 111 ms 6216 KB Output is correct
10 Correct 111 ms 6232 KB Output is correct
11 Correct 115 ms 6276 KB Output is correct
12 Correct 118 ms 6264 KB Output is correct
13 Correct 120 ms 6268 KB Output is correct
14 Correct 111 ms 6340 KB Output is correct
15 Correct 118 ms 6228 KB Output is correct
16 Correct 22 ms 4668 KB Output is correct
17 Correct 23 ms 4680 KB Output is correct
18 Correct 23 ms 4664 KB Output is correct
19 Correct 23 ms 4744 KB Output is correct
20 Correct 23 ms 4668 KB Output is correct
21 Incorrect 108 ms 6152 KB Output isn't correct
22 Halted 0 ms 0 KB -