oj.uz

Submission #985066

# Submission time Handle Problem Language Result Execution time Memory
985066 2024-05-17T10:19:15 Z siewjh Boat (APIO16_boat) C++17
0 / 100
 3 ms 4188 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll pref[505][1005], ia[505];
ll pwr(ll a, ll b){
	ll ans = 1;
	while (b){
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
ll inv(ll a){
	return pwr(a, mod - 2);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nums; cin >> nums;
	for (int i = 1; i <= nums; i++) ia[i] = inv(i);
	vector<ll> av(nums + 1), bv(nums + 1), disc; disc.push_back(-1);
	for (int i = 1; i <= nums; i++){
		ll a, b; cin >> a >> b; b++;
		av[i] = a; bv[i] = b;
		disc.push_back(a); disc.push_back(b);
	}
	sort(disc.begin(), disc.end());
	disc.resize(distance(disc.begin(), unique(disc.begin(), disc.end())));
	int segs = disc.size() - 2;
	for (int j = 0; j <= segs; j++) pref[0][j] = 1;
	ll ans = 0;
	for (int i = 1; i <= nums; i++)
		for (int j = 1; j <= segs; j++){
			ll dpv = 0, len = disc[j + 1] - disc[j];
			if (av[i] <= disc[j] && bv[i] >= disc[j + 1]){
				ll cv = len; int cnt = 1;
				for (int k = i - 1; k >= 0; k--){
					dpv = (dpv + pref[k][j - 1] * cv % mod) % mod;
					if (av[k] <= disc[j] && bv[k] >= disc[j + 1]){
						cnt++; cv = cv * (len + cnt - 1) % mod * ia[cnt] % mod;
					}
				}
			}
			pref[i][j] = pref[i][j - 1] + dpv;
			ans += dpv;
		}
	cout << ans;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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