oj.uz

Submission #461286

# Submission time Handle Problem Language Result Execution time Memory
461286 2021-08-09T16:45:36 Z wind_reaper Boat (APIO16_boat) C++17
9 / 100
 1645 ms 4420 KB 
#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/

using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************

const int MOD = 1000000007;
const int MXN = 505;

//***************** GLOBAL VARIABLES *****************

int A[MXN], B[MXN];
int64_t dp[MXN][MXN << 1], F[MXN], iF[MXN], C[MXN];

//***************** AUXILIARY STRUCTS *****************

int64_t power(int64_t n, int64_t x = MOD - 2){
	int64_t res = 1;
	while(x){
		if(x & 1)
			res = (res * n) % MOD;

		x >>= 1;
		n = (n * n) % MOD;
	}
	return res;
}

inline int64_t nCk(int n, int k){
	return F[n] * ((iF[n - k] * iF[k]) % MOD) % MOD;
}


//***************** MAIN BODY *****************

/*
	processing a range of values [D[i], D[i+1])

	we consider every [l, r] such that [1, l-1] lie in [..., D[i])
	and [l, r] lie in [D[i], D[i+1])

	> find the number of schools in [l, r] which can send boats in range [D[i], D[i+1])

	other schools are ignored

	>> add (D[i+1] - D[i]) C x where x is value calculated in >

	dp[i][j] -> insert i into j th interval

	dp[r][j] = sum(dp[l-1][j-1] + ways(l, r, j))

	ways(l, r, j) = >>

	C[i] -> no. of ways of picking up <= i items in increasing order from len items

	dp[i][j] = 
*/

void solve(){
	int N;
	cin >> N;

	vector<int> D;

	for(int i = 0; i < N; i++){
		cin >> A[i] >> B[i];
		D.push_back(A[i]);
		D.push_back(B[i] + 1);
	}

	F[0] = F[1] = 1;
	for(int i = 2; i < MXN; i++){
		F[i] = (F[i-1] * 1LL * i) % MOD;
	}

	iF[MXN - 1] = power(F[MXN - 1]);

	for(int i = MXN - 2; i >= 0; --i){
		iF[i] = (iF[i+1] * 1LL * (i + 1)) % MOD;
	}

	sort(D.begin(), D.end());
	D.erase(unique(D.begin(), D.end()), D.end());

	int n = D.size() - 1;

	int64_t ans = 0;

	for(int _ = 0; _ < n; _++){
		int len = D[_+1] - D[_];
		for(int i = 1; i <= N; i++){
			int64_t p = 1; C[i] = 0;
			for(int j = 1; j <= i; j++){
				p = (p * 1LL * (len - j + 1)) % MOD;
				C[i] = (C[i] + (((p * iF[j]) % MOD) * nCk(i - 1, j - 1)) % MOD) % MOD;
			}
		}

		for(int i = 0; i < N; i++) if(A[i] <= D[_] && B[i] >= D[_+1] - 1) {
			int cnt = 0;
			for(int j = i; j >= 0; --j){
				if(_) (dp[i][_] += dp[j][_-1] * C[cnt]) %= MOD;
				cnt += (A[j] <= D[_] && B[i] >= D[_+1] - 1);
			}
			(dp[i][_] += C[cnt]) %= MOD;
			ans = (ans + dp[i][_]) % MOD;
		}

		for(int i = 0; i < N; i++)
			(dp[i][_] += dp[i][_-1]) %= MOD;
	}

	cout << ans << '\n';
}

//***************** *****************

int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic

4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1598 ms 4292 KB Output is correct
2 Correct 1625 ms 4268 KB Output is correct
3 Correct 1623 ms 4280 KB Output is correct
4 Correct 1624 ms 4284 KB Output is correct
5 Correct 1618 ms 4288 KB Output is correct
6 Correct 1617 ms 4376 KB Output is correct
7 Correct 1618 ms 4284 KB Output is correct
8 Correct 1591 ms 4340 KB Output is correct
9 Correct 1619 ms 4284 KB Output is correct
10 Correct 1623 ms 4284 KB Output is correct
11 Correct 1610 ms 4360 KB Output is correct
12 Correct 1597 ms 4280 KB Output is correct
13 Correct 1590 ms 4296 KB Output is correct
14 Correct 1613 ms 4340 KB Output is correct
15 Correct 1614 ms 4196 KB Output is correct
16 Correct 282 ms 2948 KB Output is correct
17 Correct 305 ms 3032 KB Output is correct
18 Correct 291 ms 2960 KB Output is correct
19 Correct 306 ms 3052 KB Output is correct
20 Correct 294 ms 2972 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1598 ms 4292 KB Output is correct
2 Correct 1625 ms 4268 KB Output is correct
3 Correct 1623 ms 4280 KB Output is correct
4 Correct 1624 ms 4284 KB Output is correct
5 Correct 1618 ms 4288 KB Output is correct
6 Correct 1617 ms 4376 KB Output is correct
7 Correct 1618 ms 4284 KB Output is correct
8 Correct 1591 ms 4340 KB Output is correct
9 Correct 1619 ms 4284 KB Output is correct
10 Correct 1623 ms 4284 KB Output is correct
11 Correct 1610 ms 4360 KB Output is correct
12 Correct 1597 ms 4280 KB Output is correct
13 Correct 1590 ms 4296 KB Output is correct
14 Correct 1613 ms 4340 KB Output is correct
15 Correct 1614 ms 4196 KB Output is correct
16 Correct 282 ms 2948 KB Output is correct
17 Correct 305 ms 3032 KB Output is correct
18 Correct 291 ms 2960 KB Output is correct
19 Correct 306 ms 3052 KB Output is correct
20 Correct 294 ms 2972 KB Output is correct
21 Incorrect 1645 ms 4420 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1598 ms 4292 KB Output is correct
2 Correct 1625 ms 4268 KB Output is correct
3 Correct 1623 ms 4280 KB Output is correct
4 Correct 1624 ms 4284 KB Output is correct
5 Correct 1618 ms 4288 KB Output is correct
6 Correct 1617 ms 4376 KB Output is correct
7 Correct 1618 ms 4284 KB Output is correct
8 Correct 1591 ms 4340 KB Output is correct
9 Correct 1619 ms 4284 KB Output is correct
10 Correct 1623 ms 4284 KB Output is correct
11 Correct 1610 ms 4360 KB Output is correct
12 Correct 1597 ms 4280 KB Output is correct
13 Correct 1590 ms 4296 KB Output is correct
14 Correct 1613 ms 4340 KB Output is correct
15 Correct 1614 ms 4196 KB Output is correct
16 Correct 282 ms 2948 KB Output is correct
17 Correct 305 ms 3032 KB Output is correct
18 Correct 291 ms 2960 KB Output is correct
19 Correct 306 ms 3052 KB Output is correct
20 Correct 294 ms 2972 KB Output is correct
21 Incorrect 1645 ms 4420 KB Output isn't correct
22 Halted 0 ms 0 KB -