oj.uz

Submission #107711

# Submission time Handle Problem Language Result Execution time Memory
107711 2019-04-25T14:14:35 Z Minnakhmetov Boat (APIO16_boat) C++14
27 / 100
 1008 ms 4476 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;
}
//
//
//const int M1 = 1e3 + 5, N1 = 10;
//int dpb[N1][M1];
//
//int slow() {
//	dpb[0][0] = 1;
//	int q = 0;
//	for (int i = 0; i < n; i++) {
//		for (int j = 0; j < M1; j++) {
//			f(dpb[i + 1][j], dpb[i][j]);
//		}
//		for (int j = 1; j < M1; j++) {
//			f(dpb[i][j], dpb[i][j - 1]);
//		}
//		for (int j = a[i]; j <= b[i]; j++) {
//			f(dpb[i + 1][j], dpb[i][j - 1]);
//		}
//	}
//
//	for (int j = 1; j < M1; j++) {
//		f(dpb[n][j], dpb[n][j - 1]);
//	}
//
//	return dpb[n][M1 - 1] - 1;
//}

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 = 1; 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 1008 ms 4476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1008 ms 4476 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 14 ms 2176 KB Output is correct
2 Correct 17 ms 2176 KB Output is correct
3 Correct 16 ms 2176 KB Output is correct
4 Correct 15 ms 2176 KB Output is correct
5 Correct 19 ms 2176 KB Output is correct
6 Correct 14 ms 2176 KB Output is correct
7 Correct 17 ms 2176 KB Output is correct
8 Correct 17 ms 2176 KB Output is correct
9 Correct 18 ms 2176 KB Output is correct
10 Correct 15 ms 2176 KB Output is correct
11 Correct 15 ms 2204 KB Output is correct
12 Correct 16 ms 2304 KB Output is correct
13 Correct 7 ms 2176 KB Output is correct
14 Correct 15 ms 2176 KB Output is correct
15 Correct 19 ms 2148 KB Output is correct
16 Correct 10 ms 1920 KB Output is correct
17 Correct 11 ms 2048 KB Output is correct
18 Correct 12 ms 2048 KB Output is correct
19 Correct 12 ms 2048 KB Output is correct
20 Correct 12 ms 2048 KB Output is correct

Subtask #4
0 / 42.0

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