oj.uz

Submission #108225

# Submission time Handle Problem Language Result Execution time Memory
108225 2019-04-28T09:29:37 Z polyfish Boat (APIO16_boat) C++14
0 / 100
 128 ms 4344 KB 
//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "boat"

const int MAX_N = 502;
const int MOD = 1000000007;

int n, l[MAX_N], r[MAX_N];
vector<pair<int, int> > seg;
int64_t inv[MAX_N], f[MAX_N][MAX_N], ps[MAX_N][MAX_N];

void read_input() {
	cin >> n;

	for (int i=1; i<=n; ++i)
		cin >> l[i] >> r[i];
}

void init() {
	vector<int> x;

	for (int i=1; i<=n; ++i) {
		x.push_back(l[i]);
		x.push_back(r[i]+1);
	}

	sort(x.begin(), x.end());
	x.resize(unique(x.begin(), x.end()) - x.begin());

	seg.push_back({0, 0});
	for (int i=0; i+1<x.size(); ++i) {
		seg.push_back({x[i], x[i+1]-1});
		// cerr << seg.back().first << ' ' << seg.back().second << '\n';
	}

	inv[1] = 1;
	for (int i=2; i<=n; ++i)
		inv[i] = MOD - MOD/i*inv[MOD%i]%MOD;
	// debug(inv[2]*2%MOD);
}

int64_t C(int n, int k) {
	int64_t res = 1;

	for (int i=n-k+1; i<=n; ++i)
		res = res * i % MOD;

	return res * inv[k] % MOD;
}

bool contain(int u, int v, int l, int r) {
	return (u<=l && r<=v);
}

void dp() {
	for (int i=0; i<seg.size(); ++i)
		f[0][i] = ps[0][i] = 1;

	int64_t res = 0;

	for (int i=1; i<=n; ++i) {
		for (int j=1; j<seg.size(); ++j) {
			f[i][j] = f[i][j-1];
			for (int k=i; k>=1; --k) {
				if (!contain(l[i], r[i], seg[j].first, seg[j].second))
					break;
				// if (i==2 && j==1 && k==2)
				// 	debug(ps[k-1][j-1]);
				f[i][j] = (f[i][j] + ps[k-1][j-1] * C(seg[j].second-seg[j].first+1, i-k+1)) % MOD;
			}
		}
	
		for (int j=0; j<seg.size(); ++j)
			ps[i][j] = (ps[i-1][j] + f[i][j]) % MOD;
	}
	// debug(f[2][1]);

	cout << (ps[n][seg.size()-1] - 1 + MOD) % MOD;
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);

	read_input();
	init();
	dp();
}

Compilation message

boat.cpp: In function 'void init()':
boat.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i+1<x.size(); ++i) {
                ~~~^~~~~~~~~
boat.cpp: In function 'void dp()':
boat.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<seg.size(); ++i)
                ~^~~~~~~~~~~
boat.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1; j<seg.size(); ++j) {
                 ~^~~~~~~~~~~
boat.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<seg.size(); ++j)
                 ~^~~~~~~~~~~
boat.cpp:66:10: warning: unused variable 'res' [-Wunused-variable]
  int64_t res = 0;
          ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 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 128 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 58 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

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