oj.uz

Submission #461289

# Submission time Handle Problem Language Result Execution time Memory
461289 2021-08-09T16:48:13 Z wind_reaper Boat (APIO16_boat) C++17
9 / 100
 1674 ms 4372 KB 
// #pragma GCC Optimize "trapv"
#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 = 1;
			for(int j = i; --j >= 0;){
				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 1619 ms 4372 KB Output is correct
2 Correct 1603 ms 4344 KB Output is correct
3 Correct 1599 ms 4272 KB Output is correct
4 Correct 1618 ms 4348 KB Output is correct
5 Correct 1605 ms 4268 KB Output is correct
6 Correct 1605 ms 4272 KB Output is correct
7 Correct 1600 ms 4268 KB Output is correct
8 Correct 1592 ms 4272 KB Output is correct
9 Correct 1594 ms 4304 KB Output is correct
10 Correct 1659 ms 4272 KB Output is correct
11 Correct 1594 ms 4320 KB Output is correct
12 Correct 1668 ms 4268 KB Output is correct
13 Correct 1650 ms 4272 KB Output is correct
14 Correct 1651 ms 4344 KB Output is correct
15 Correct 1607 ms 4356 KB Output is correct
16 Correct 287 ms 3268 KB Output is correct
17 Correct 302 ms 3060 KB Output is correct
18 Correct 306 ms 3132 KB Output is correct
19 Correct 306 ms 2976 KB Output is correct
20 Correct 297 ms 3000 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1619 ms 4372 KB Output is correct
2 Correct 1603 ms 4344 KB Output is correct
3 Correct 1599 ms 4272 KB Output is correct
4 Correct 1618 ms 4348 KB Output is correct
5 Correct 1605 ms 4268 KB Output is correct
6 Correct 1605 ms 4272 KB Output is correct
7 Correct 1600 ms 4268 KB Output is correct
8 Correct 1592 ms 4272 KB Output is correct
9 Correct 1594 ms 4304 KB Output is correct
10 Correct 1659 ms 4272 KB Output is correct
11 Correct 1594 ms 4320 KB Output is correct
12 Correct 1668 ms 4268 KB Output is correct
13 Correct 1650 ms 4272 KB Output is correct
14 Correct 1651 ms 4344 KB Output is correct
15 Correct 1607 ms 4356 KB Output is correct
16 Correct 287 ms 3268 KB Output is correct
17 Correct 302 ms 3060 KB Output is correct
18 Correct 306 ms 3132 KB Output is correct
19 Correct 306 ms 2976 KB Output is correct
20 Correct 297 ms 3000 KB Output is correct
21 Incorrect 1674 ms 4176 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 1619 ms 4372 KB Output is correct
2 Correct 1603 ms 4344 KB Output is correct
3 Correct 1599 ms 4272 KB Output is correct
4 Correct 1618 ms 4348 KB Output is correct
5 Correct 1605 ms 4268 KB Output is correct
6 Correct 1605 ms 4272 KB Output is correct
7 Correct 1600 ms 4268 KB Output is correct
8 Correct 1592 ms 4272 KB Output is correct
9 Correct 1594 ms 4304 KB Output is correct
10 Correct 1659 ms 4272 KB Output is correct
11 Correct 1594 ms 4320 KB Output is correct
12 Correct 1668 ms 4268 KB Output is correct
13 Correct 1650 ms 4272 KB Output is correct
14 Correct 1651 ms 4344 KB Output is correct
15 Correct 1607 ms 4356 KB Output is correct
16 Correct 287 ms 3268 KB Output is correct
17 Correct 302 ms 3060 KB Output is correct
18 Correct 306 ms 3132 KB Output is correct
19 Correct 306 ms 2976 KB Output is correct
20 Correct 297 ms 3000 KB Output is correct
21 Incorrect 1674 ms 4176 KB Output isn't correct
22 Halted 0 ms 0 KB -