oj.uz

Submission #447811

# Submission time Handle Problem Language Result Execution time Memory
447811 2021-07-27T14:59:05 Z dutch Boat (APIO16_boat) C++17
9 / 100
 2000 ms 4412 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MOD = 1e9+7, LIM = 501;

int modInverse(int x){
	int r = 1, p = (MOD - 2) * 2;
	for(int y=x; p/=2; y=(y*y) % MOD)
		if(p & 1) r = (r*y) % MOD;
	return r;
}

int n, a[LIM], b[LIM], dp[LIM][LIM*2], F[LIM], invF[LIM], C[LIM];
bool valid[LIM];
vector<int> pts;

int nCr(int x, int y){
	return (((F[x] * invF[y]) % MOD) * invF[x-y]) % MOD;
}

void add(int &x, int y){
	x += y;
	while(x >= MOD) x -= MOD;
	while(x <=-MOD) x += MOD;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);

	cin >> n;
	for(int i=0; i<n; ++i){
		cin >> a[i] >> b[i];
		pts.push_back(a[i]);
		pts.push_back(b[i]+1);
	}
	sort(pts.begin(), pts.end());
	pts.resize(unique(pts.begin(), pts.end()) - pts.begin());

	int m = size(pts) - 1, ans = 0;

	F[0] = invF[0] = 1;
	for(int i=1; i<=n; ++i){
		F[i] = (F[i-1] * i) % MOD;
		invF[i] = modInverse(F[i]);
	}
	for(int k=0; k<m; ++k){
		for(int i=1; i<=n; ++i){
			int p = 1; C[i] = 0;
			for(int j=1; j<=i; ++j){
				(p *= pts[k+1] - pts[k] - j + 1) %= MOD;
				(C[i] += ((p * invF[j]) % MOD) * nCr(i-1, j-1)) %= MOD;
			}
		}
		for(int i=0; i<n; ++i){
			valid[i] = a[i] <= pts[k] && pts[k+1] <= b[i]+1;
		}
		for(int i=0; i<n; ++i){
			if(valid[i]){
				int cnt = 1;
				for(int j=i; --j>=0; ){
					if(k) add(dp[i][k], dp[j][k-1] * C[cnt]);
					cnt += valid[j];
				}
				add(dp[i][k], C[cnt]);
				add(ans, dp[i][k]);
			}
			if(k){
				add(dp[i][k], dp[i][k-1]);
			}
		}
	}
	cout << (ans % MOD + MOD) % MOD;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1322 ms 4172 KB Output is correct
2 Correct 1349 ms 4256 KB Output is correct
3 Correct 1331 ms 4260 KB Output is correct
4 Correct 1330 ms 4212 KB Output is correct
5 Correct 1379 ms 4252 KB Output is correct
6 Correct 1326 ms 4256 KB Output is correct
7 Correct 1331 ms 4316 KB Output is correct
8 Correct 1332 ms 4320 KB Output is correct
9 Correct 1330 ms 4408 KB Output is correct
10 Correct 1323 ms 4260 KB Output is correct
11 Correct 1330 ms 4260 KB Output is correct
12 Correct 1358 ms 4272 KB Output is correct
13 Correct 1372 ms 4412 KB Output is correct
14 Correct 1325 ms 4152 KB Output is correct
15 Correct 1324 ms 4292 KB Output is correct
16 Correct 234 ms 2884 KB Output is correct
17 Correct 249 ms 2956 KB Output is correct
18 Correct 247 ms 2912 KB Output is correct
19 Correct 249 ms 3008 KB Output is correct
20 Correct 248 ms 3012 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1322 ms 4172 KB Output is correct
2 Correct 1349 ms 4256 KB Output is correct
3 Correct 1331 ms 4260 KB Output is correct
4 Correct 1330 ms 4212 KB Output is correct
5 Correct 1379 ms 4252 KB Output is correct
6 Correct 1326 ms 4256 KB Output is correct
7 Correct 1331 ms 4316 KB Output is correct
8 Correct 1332 ms 4320 KB Output is correct
9 Correct 1330 ms 4408 KB Output is correct
10 Correct 1323 ms 4260 KB Output is correct
11 Correct 1330 ms 4260 KB Output is correct
12 Correct 1358 ms 4272 KB Output is correct
13 Correct 1372 ms 4412 KB Output is correct
14 Correct 1325 ms 4152 KB Output is correct
15 Correct 1324 ms 4292 KB Output is correct
16 Correct 234 ms 2884 KB Output is correct
17 Correct 249 ms 2956 KB Output is correct
18 Correct 247 ms 2912 KB Output is correct
19 Correct 249 ms 3008 KB Output is correct
20 Correct 248 ms 3012 KB Output is correct
21 Execution timed out 2090 ms 2412 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1322 ms 4172 KB Output is correct
2 Correct 1349 ms 4256 KB Output is correct
3 Correct 1331 ms 4260 KB Output is correct
4 Correct 1330 ms 4212 KB Output is correct
5 Correct 1379 ms 4252 KB Output is correct
6 Correct 1326 ms 4256 KB Output is correct
7 Correct 1331 ms 4316 KB Output is correct
8 Correct 1332 ms 4320 KB Output is correct
9 Correct 1330 ms 4408 KB Output is correct
10 Correct 1323 ms 4260 KB Output is correct
11 Correct 1330 ms 4260 KB Output is correct
12 Correct 1358 ms 4272 KB Output is correct
13 Correct 1372 ms 4412 KB Output is correct
14 Correct 1325 ms 4152 KB Output is correct
15 Correct 1324 ms 4292 KB Output is correct
16 Correct 234 ms 2884 KB Output is correct
17 Correct 249 ms 2956 KB Output is correct
18 Correct 247 ms 2912 KB Output is correct
19 Correct 249 ms 3008 KB Output is correct
20 Correct 248 ms 3012 KB Output is correct
21 Execution timed out 2090 ms 2412 KB Time limit exceeded
22 Halted 0 ms 0 KB -