oj.uz

Submission #1031393

# Submission time Handle Problem Language Result Execution time Memory
1031393 2024-07-22T19:14:11 Z Tob Boat (APIO16_boat) C++14
9 / 100
 432 ms 7516 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

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

int add(int x, int y) {return (x+y < mod) ? x+y : x+y-mod;}
int mul(int x, int y) {return (ll)x*y%mod;}

int n;
int aa[N], bb[N], a[N], b[N], dp[N][2*N], ch[N][2*N], c[N][2*N], inv[N], cho[N][N];

int Pow(int x, int y) {
	int res = 1, pot = x;
	while (y) {
		if (y % 2) res = mul(res, pot);
		pot = mul(pot, pot);
		y /= 2;
	}
	return res;
}

int main () {
	FIO;
	inv[0] = 1;
	for (int i = 1; i < N; i++) inv[i] = Pow(i, mod-2);
	for (int i = 0; i < N; i++) {
		cho[i][0] = 1;
		for (int j = 1; j < i; j++) cho[i][j] = add(cho[i-1][j], cho[i-1][j-1]);
	}
	cin >> n;
	vector <int> v;
	map <int, int> saz;
	for (int i = 0; i < n; i++) {
		cin >> aa[i] >> bb[i]; bb[i]++;
		v.pb(aa[i]);
		v.pb(bb[i]);
	}
	sort(all(v)); v.erase(unique(all(v)), v.end());
	int siz = v.size()-1;
	for (int i = 0; i <= siz; i++) saz[v[i]] = i;
	for (int i = 0; i < n; i++) {
		a[i] = saz[aa[i]];
		b[i] = saz[bb[i]];
	}
	for (int i = 0; i < siz; i++) {
		int x = v[i+1]-v[i];
		for (int j = 1; j <= min(n,x); j++) {
			int pro = 1;
			for (int k = x, l = 1; k > x-j; k--, l++) pro = mul(pro, mul(k, inv[l]));
			ch[j][i] = pro;
		}
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= min(j,x); k++) {
				c[j][i] = add(c[j][i], mul(ch[k][i], cho[j-1][k-1]));
			}
		}
	}
	for (int j = 0; j < siz; j++) {
		for (int i = 0; i < n; i++) {
			if (j) dp[i][j] = dp[i][j-1];
			if (j < a[i] || j >= b[i]) continue;
			int cnt = 1;
			for (int k = i-1; k >= 0; k--) {
				dp[i][j] = add(dp[i][j], mul(c[cnt][j], dp[k][j-1]));
				cnt += (j >= a[k] && j < b[k]);
				cnt -= (cnt > v[j+1]-v[j]);
			}
			dp[i][j] = add(dp[i][j], c[cnt][j]);
		}
	}
	
	int res = 0;
	for (int i = 0; i < n; i++) res = add(res, dp[i][siz-1]);
	
	cout << res;

	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 7508 KB Output is correct
2 Correct 403 ms 7504 KB Output is correct
3 Correct 421 ms 7356 KB Output is correct
4 Correct 419 ms 7360 KB Output is correct
5 Correct 421 ms 7508 KB Output is correct
6 Correct 403 ms 7360 KB Output is correct
7 Correct 406 ms 7508 KB Output is correct
8 Correct 395 ms 7508 KB Output is correct
9 Correct 430 ms 7348 KB Output is correct
10 Correct 416 ms 7356 KB Output is correct
11 Correct 420 ms 7352 KB Output is correct
12 Correct 432 ms 7360 KB Output is correct
13 Correct 410 ms 7504 KB Output is correct
14 Correct 420 ms 7348 KB Output is correct
15 Correct 409 ms 7504 KB Output is correct
16 Correct 76 ms 7312 KB Output is correct
17 Correct 84 ms 7324 KB Output is correct
18 Correct 80 ms 7248 KB Output is correct
19 Correct 83 ms 7308 KB Output is correct
20 Correct 81 ms 7252 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 7508 KB Output is correct
2 Correct 403 ms 7504 KB Output is correct
3 Correct 421 ms 7356 KB Output is correct
4 Correct 419 ms 7360 KB Output is correct
5 Correct 421 ms 7508 KB Output is correct
6 Correct 403 ms 7360 KB Output is correct
7 Correct 406 ms 7508 KB Output is correct
8 Correct 395 ms 7508 KB Output is correct
9 Correct 430 ms 7348 KB Output is correct
10 Correct 416 ms 7356 KB Output is correct
11 Correct 420 ms 7352 KB Output is correct
12 Correct 432 ms 7360 KB Output is correct
13 Correct 410 ms 7504 KB Output is correct
14 Correct 420 ms 7348 KB Output is correct
15 Correct 409 ms 7504 KB Output is correct
16 Correct 76 ms 7312 KB Output is correct
17 Correct 84 ms 7324 KB Output is correct
18 Correct 80 ms 7248 KB Output is correct
19 Correct 83 ms 7308 KB Output is correct
20 Correct 81 ms 7252 KB Output is correct
21 Incorrect 180 ms 7516 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 7508 KB Output is correct
2 Correct 403 ms 7504 KB Output is correct
3 Correct 421 ms 7356 KB Output is correct
4 Correct 419 ms 7360 KB Output is correct
5 Correct 421 ms 7508 KB Output is correct
6 Correct 403 ms 7360 KB Output is correct
7 Correct 406 ms 7508 KB Output is correct
8 Correct 395 ms 7508 KB Output is correct
9 Correct 430 ms 7348 KB Output is correct
10 Correct 416 ms 7356 KB Output is correct
11 Correct 420 ms 7352 KB Output is correct
12 Correct 432 ms 7360 KB Output is correct
13 Correct 410 ms 7504 KB Output is correct
14 Correct 420 ms 7348 KB Output is correct
15 Correct 409 ms 7504 KB Output is correct
16 Correct 76 ms 7312 KB Output is correct
17 Correct 84 ms 7324 KB Output is correct
18 Correct 80 ms 7248 KB Output is correct
19 Correct 83 ms 7308 KB Output is correct
20 Correct 81 ms 7252 KB Output is correct
21 Incorrect 180 ms 7516 KB Output isn't correct
22 Halted 0 ms 0 KB -