oj.uz

Submission #1031379

# Submission time Handle Problem Language Result Execution time Memory
1031379 2024-07-22T18:47:17 Z Tob Boat (APIO16_boat) C++14
0 / 100
 832 ms 7304 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 <= n; j++) {
			int pro = 1;
			for (int k = x-1+j, l = 1; k >= x; 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 <= j; 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]);
			}
			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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 7284 KB Output is correct
2 Correct 832 ms 7284 KB Output is correct
3 Correct 800 ms 7304 KB Output is correct
4 Correct 821 ms 7292 KB Output is correct
5 Correct 786 ms 7248 KB Output is correct
6 Correct 780 ms 7288 KB Output is correct
7 Correct 758 ms 7252 KB Output is correct
8 Correct 796 ms 7296 KB Output is correct
9 Correct 766 ms 7248 KB Output is correct
10 Correct 772 ms 7296 KB Output is correct
11 Correct 790 ms 7252 KB Output is correct
12 Correct 760 ms 7288 KB Output is correct
13 Correct 761 ms 7252 KB Output is correct
14 Correct 769 ms 7292 KB Output is correct
15 Correct 745 ms 7288 KB Output is correct
16 Incorrect 141 ms 7248 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 7284 KB Output is correct
2 Correct 832 ms 7284 KB Output is correct
3 Correct 800 ms 7304 KB Output is correct
4 Correct 821 ms 7292 KB Output is correct
5 Correct 786 ms 7248 KB Output is correct
6 Correct 780 ms 7288 KB Output is correct
7 Correct 758 ms 7252 KB Output is correct
8 Correct 796 ms 7296 KB Output is correct
9 Correct 766 ms 7248 KB Output is correct
10 Correct 772 ms 7296 KB Output is correct
11 Correct 790 ms 7252 KB Output is correct
12 Correct 760 ms 7288 KB Output is correct
13 Correct 761 ms 7252 KB Output is correct
14 Correct 769 ms 7292 KB Output is correct
15 Correct 745 ms 7288 KB Output is correct
16 Incorrect 141 ms 7248 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 7284 KB Output is correct
2 Correct 832 ms 7284 KB Output is correct
3 Correct 800 ms 7304 KB Output is correct
4 Correct 821 ms 7292 KB Output is correct
5 Correct 786 ms 7248 KB Output is correct
6 Correct 780 ms 7288 KB Output is correct
7 Correct 758 ms 7252 KB Output is correct
8 Correct 796 ms 7296 KB Output is correct
9 Correct 766 ms 7248 KB Output is correct
10 Correct 772 ms 7296 KB Output is correct
11 Correct 790 ms 7252 KB Output is correct
12 Correct 760 ms 7288 KB Output is correct
13 Correct 761 ms 7252 KB Output is correct
14 Correct 769 ms 7292 KB Output is correct
15 Correct 745 ms 7288 KB Output is correct
16 Incorrect 141 ms 7248 KB Output isn't correct
17 Halted 0 ms 0 KB -