oj.uz

Submission #48519

# Submission time Handle Problem Language Result Execution time Memory
48519 2018-05-15T12:42:15 Z Kmcode Boat (APIO16_boat) C++14
9 / 100
 831 ms 18788 KB 
#include "bits/stdc++.h"
using namespace std;

#define MOD 1000000007

#define MAX 1102


int n;

vector<pair<int, int> > v;
vector<int> vv;

int dp[MAX][MAX];

long long int way[MAX][MAX];

long long int c[MAX][MAX];

long long int ppow(long long int i, long long int j) {
	long long int res = 1;
	while (j) {
		if ((j & 1LL)) {
			res *= i;
			if (res >= MOD)res %= MOD;
		}
		i *= i;
		if (i >= MOD)i %= MOD;
		j >>= 1LL;
	}
	return res;
}

long long int k[MAX];

int main() {
	k[0] = 1;
	for (int i = 1; i < MAX; i++) {
		k[i] = k[i - 1];
		k[i] *= (long long int)(i);
		if (k[i] >= MOD)k[i] %= MOD;
	}
	for (int i = 0; i < MAX; i++) {
		k[i] = ppow(k[i], MOD - 2);
	}
	c[0][0] = 1;
	for (int i = 0; i + 1 < MAX; i++) {
		for (int j = 0; j <= i; j++) {
			c[i + 1][j] += c[i][j];
			c[i + 1][j + 1] += c[i][j];
			if (c[i + 1][j] >= MOD)c[i + 1][j] -= MOD;
			if (c[i + 1][j + 1] >= MOD)c[i + 1][j + 1] -= MOD;
		}
	}
	cin >> n;
	vv.push_back(0);
	for (int i = 0; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		vv.push_back(a), vv.push_back(b+1);
		v.push_back(make_pair(a, b));
	}
	sort(vv.begin(), vv.end());
	vv.erase(unique(vv.begin(), vv.end()), vv.end());
	vv.push_back(vv.back() + 1);
	dp[0][0] = 1;
	for (int i = 0; i + 1 < vv.size(); i++) {
		long long int rng = vv[i + 1] - vv[i];
		long long int up = 1;
		long long int dw = 0;
		for (int j = 1; j <= 500; j++) {
			if (rng < j)break;
			up *= (long long int)(rng - j + 1LL);
			dw = k[j];
			dw *= up;
			if (dw >= MOD)dw %= MOD;
			way[i][j] = dw;
		}
		for (int j = 500; j >= 1; j--) {
			long long int tmp = 0;
			for (int k = j; k >= 1; k--) {
				tmp += way[i][k] * c[j - 1][k - 1];
				if (tmp >= MOD)tmp %= MOD;
			}
			way[i][j] = tmp;
		}
	}
	long long int AA = 0;
	for (int i = 0; i < v.size(); i++) {
		long long int su = 0;
		for (int j = 0; j + 1 < vv.size(); j++) {
			int valid = 0;
			for (int k = i; k < v.size(); k++) {
				if (v[k].first <= vv[j] && vv[j + 1] - 1 <= v[k].second) {
					valid++;
					dp[k + 1][j] += su*way[j][valid];
					AA += su*way[j][valid];
					if (AA >= MOD)AA %= MOD;
					if (dp[k + 1][j] >= MOD)dp[k + 1][j] %= MOD;
				}
			}
			su += dp[i][j];
			if (su >= MOD)su -= MOD;
		}
	}
	printf("%lld\n", AA);
	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:67:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < vv.size(); i++) {
                  ~~~~~~^~~~~~~~~~~
boat.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
boat.cpp:91:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vv.size(); j++) {
                   ~~~~~~^~~~~~~~~~~
boat.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = i; k < v.size(); k++) {
                    ~~^~~~~~~~~~
boat.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 18364 KB Output is correct
2 Correct 692 ms 18364 KB Output is correct
3 Correct 682 ms 18460 KB Output is correct
4 Correct 702 ms 18460 KB Output is correct
5 Correct 707 ms 18536 KB Output is correct
6 Correct 397 ms 18536 KB Output is correct
7 Correct 384 ms 18744 KB Output is correct
8 Correct 409 ms 18744 KB Output is correct
9 Correct 400 ms 18784 KB Output is correct
10 Correct 391 ms 18788 KB Output is correct
11 Correct 412 ms 18788 KB Output is correct
12 Correct 419 ms 18788 KB Output is correct
13 Correct 411 ms 18788 KB Output is correct
14 Correct 395 ms 18788 KB Output is correct
15 Correct 399 ms 18788 KB Output is correct
16 Correct 132 ms 18788 KB Output is correct
17 Correct 137 ms 18788 KB Output is correct
18 Correct 133 ms 18788 KB Output is correct
19 Correct 140 ms 18788 KB Output is correct
20 Correct 135 ms 18788 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 18364 KB Output is correct
2 Correct 692 ms 18364 KB Output is correct
3 Correct 682 ms 18460 KB Output is correct
4 Correct 702 ms 18460 KB Output is correct
5 Correct 707 ms 18536 KB Output is correct
6 Correct 397 ms 18536 KB Output is correct
7 Correct 384 ms 18744 KB Output is correct
8 Correct 409 ms 18744 KB Output is correct
9 Correct 400 ms 18784 KB Output is correct
10 Correct 391 ms 18788 KB Output is correct
11 Correct 412 ms 18788 KB Output is correct
12 Correct 419 ms 18788 KB Output is correct
13 Correct 411 ms 18788 KB Output is correct
14 Correct 395 ms 18788 KB Output is correct
15 Correct 399 ms 18788 KB Output is correct
16 Correct 132 ms 18788 KB Output is correct
17 Correct 137 ms 18788 KB Output is correct
18 Correct 133 ms 18788 KB Output is correct
19 Correct 140 ms 18788 KB Output is correct
20 Correct 135 ms 18788 KB Output is correct
21 Incorrect 831 ms 18788 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 18364 KB Output is correct
2 Correct 692 ms 18364 KB Output is correct
3 Correct 682 ms 18460 KB Output is correct
4 Correct 702 ms 18460 KB Output is correct
5 Correct 707 ms 18536 KB Output is correct
6 Correct 397 ms 18536 KB Output is correct
7 Correct 384 ms 18744 KB Output is correct
8 Correct 409 ms 18744 KB Output is correct
9 Correct 400 ms 18784 KB Output is correct
10 Correct 391 ms 18788 KB Output is correct
11 Correct 412 ms 18788 KB Output is correct
12 Correct 419 ms 18788 KB Output is correct
13 Correct 411 ms 18788 KB Output is correct
14 Correct 395 ms 18788 KB Output is correct
15 Correct 399 ms 18788 KB Output is correct
16 Correct 132 ms 18788 KB Output is correct
17 Correct 137 ms 18788 KB Output is correct
18 Correct 133 ms 18788 KB Output is correct
19 Correct 140 ms 18788 KB Output is correct
20 Correct 135 ms 18788 KB Output is correct
21 Incorrect 831 ms 18788 KB Output isn't correct
22 Halted 0 ms 0 KB -