oj.uz

Submission #107699

# Submission time Handle Problem Language Result Execution time Memory
107699 2019-04-25T13:38:42 Z Minnakhmetov Boat (APIO16_boat) C++14
0 / 100
 1335 ms 4344 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define ull unsigned long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

const int N = 505, MOD = 1e9 + 7;
int a[N], b[N], dp[N][N * 2], dp2[N][N], c[N][N], c2[N];

ll bp(ll a, ll p) {
	ll r = 1;
	while (p > 0) {
		if (p & 1)
			r = r * a % MOD;
		p >>= 1;
		a = a * a % MOD;
	}
	return r;
}

void f(int& a, int b) {
	a += b;
	if (a >= MOD)
		a -= MOD;
}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);


	for (int i = 0; i < N; i++) {
		c[i][0] = 1;
	}

	for (int i = 1; i < N; i++) {
		for (int j = 1; j < N; j++) {
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
		}
	}

	int n;
	cin >> n;
	
	vector<int> v;
	v.push_back(0);

	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		v.push_back(a[i]);
		v.push_back(b[i] + 1);
	}

	sort(all(v));
	v.erase(unique(all(v)), v.end());

	int m = v.size() - 1;


	for (int i = 1; i < m; i++) {
		ll t = 1;
		for (int j = 0; j <= n; j++) {
			c2[j] = t;
			t = t * (v[i + 1] - v[i] - j) % MOD * bp(j + 1, MOD - 2) % MOD;
		}
		for (int j = 0; j <= n; j++) {
			for (int h = 1; h <= j; h++) {
				dp2[i][j] = (dp2[i][j] + c[j][h] * (ll)c2[h]) % MOD;
			}
		}
	}
	
	dp[0][0] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m; j++) {
			f(dp[i][j], dp[i][j - 1]);
			int g = 0;
			for (int k = i; k < n; k++) {
				if (a[k] <= v[j] && b[k] >= v[j + 1] - 1)
					g++;
				dp[k + 1][j] = (dp[k + 1][j] + dp[i][j - 1] * (ll)dp2[j][g]) % MOD;
			}
		}
	}

	int ans = 0;
	for (int i = 1; i < m; i++)
		f(ans, dp[n][i]);
	cout << ans;

	return 0;
}

Compilation message

boat.cpp:42:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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