oj.uz

Submission #461287

# Submission time Handle Problem Language Result Execution time Memory
461287 2021-08-09T16:47:05 Z wind_reaper Boat (APIO16_boat) C++17
9 / 100
 1660 ms 4380 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 = 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
*/

Compilation message

boat.cpp:1: warning: ignoring '#pragma GCC Optimize' [-Wunknown-pragmas]
    1 | #pragma GCC Optimize "trapv"
      |

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1591 ms 4380 KB Output is correct
2 Correct 1577 ms 4284 KB Output is correct
3 Correct 1623 ms 4364 KB Output is correct
4 Correct 1607 ms 4272 KB Output is correct
5 Correct 1599 ms 4336 KB Output is correct
6 Correct 1660 ms 4172 KB Output is correct
7 Correct 1632 ms 4344 KB Output is correct
8 Correct 1614 ms 4352 KB Output is correct
9 Correct 1604 ms 4268 KB Output is correct
10 Correct 1639 ms 4240 KB Output is correct
11 Correct 1623 ms 4164 KB Output is correct
12 Correct 1601 ms 4236 KB Output is correct
13 Correct 1625 ms 4272 KB Output is correct
14 Correct 1612 ms 4304 KB Output is correct
15 Correct 1594 ms 4364 KB Output is correct
16 Correct 282 ms 2952 KB Output is correct
17 Correct 303 ms 3036 KB Output is correct
18 Correct 297 ms 3068 KB Output is correct
19 Correct 303 ms 3092 KB Output is correct
20 Correct 297 ms 3152 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1591 ms 4380 KB Output is correct
2 Correct 1577 ms 4284 KB Output is correct
3 Correct 1623 ms 4364 KB Output is correct
4 Correct 1607 ms 4272 KB Output is correct
5 Correct 1599 ms 4336 KB Output is correct
6 Correct 1660 ms 4172 KB Output is correct
7 Correct 1632 ms 4344 KB Output is correct
8 Correct 1614 ms 4352 KB Output is correct
9 Correct 1604 ms 4268 KB Output is correct
10 Correct 1639 ms 4240 KB Output is correct
11 Correct 1623 ms 4164 KB Output is correct
12 Correct 1601 ms 4236 KB Output is correct
13 Correct 1625 ms 4272 KB Output is correct
14 Correct 1612 ms 4304 KB Output is correct
15 Correct 1594 ms 4364 KB Output is correct
16 Correct 282 ms 2952 KB Output is correct
17 Correct 303 ms 3036 KB Output is correct
18 Correct 297 ms 3068 KB Output is correct
19 Correct 303 ms 3092 KB Output is correct
20 Correct 297 ms 3152 KB Output is correct
21 Incorrect 1629 ms 4268 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 1591 ms 4380 KB Output is correct
2 Correct 1577 ms 4284 KB Output is correct
3 Correct 1623 ms 4364 KB Output is correct
4 Correct 1607 ms 4272 KB Output is correct
5 Correct 1599 ms 4336 KB Output is correct
6 Correct 1660 ms 4172 KB Output is correct
7 Correct 1632 ms 4344 KB Output is correct
8 Correct 1614 ms 4352 KB Output is correct
9 Correct 1604 ms 4268 KB Output is correct
10 Correct 1639 ms 4240 KB Output is correct
11 Correct 1623 ms 4164 KB Output is correct
12 Correct 1601 ms 4236 KB Output is correct
13 Correct 1625 ms 4272 KB Output is correct
14 Correct 1612 ms 4304 KB Output is correct
15 Correct 1594 ms 4364 KB Output is correct
16 Correct 282 ms 2952 KB Output is correct
17 Correct 303 ms 3036 KB Output is correct
18 Correct 297 ms 3068 KB Output is correct
19 Correct 303 ms 3092 KB Output is correct
20 Correct 297 ms 3152 KB Output is correct
21 Incorrect 1629 ms 4268 KB Output isn't correct
22 Halted 0 ms 0 KB -