oj.uz

Submission #107710

# Submission time Handle Problem Language Result Execution time Memory
107710 2019-04-25T14:12:02 Z Minnakhmetov Boat (APIO16_boat) C++14
27 / 100
 1014 ms 4600 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];
int 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;
		}
	}


	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 - 1][h - 1] * (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]);
	}
	for (int i = 1; i < n; i++) {
		f(ans, dp[i][m - 1]);
	}
	cout << ans;


	//cout << "\n" << slow();

	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 1014 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2176 KB Output is correct
2 Correct 14 ms 2176 KB Output is correct
3 Correct 15 ms 2176 KB Output is correct
4 Correct 15 ms 2176 KB Output is correct
5 Correct 17 ms 2048 KB Output is correct
6 Correct 19 ms 2176 KB Output is correct
7 Correct 16 ms 2176 KB Output is correct
8 Correct 18 ms 2176 KB Output is correct
9 Correct 15 ms 2176 KB Output is correct
10 Correct 16 ms 2176 KB Output is correct
11 Correct 17 ms 2092 KB Output is correct
12 Correct 16 ms 2304 KB Output is correct
13 Correct 15 ms 2176 KB Output is correct
14 Correct 17 ms 2176 KB Output is correct
15 Correct 17 ms 2176 KB Output is correct
16 Correct 12 ms 1920 KB Output is correct
17 Correct 12 ms 1920 KB Output is correct
18 Correct 11 ms 1920 KB Output is correct
19 Correct 11 ms 1920 KB Output is correct
20 Correct 10 ms 2048 KB Output is correct

Subtask #4
0 / 42.0

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