oj.uz

Submission #48520

# Submission time Handle Problem Language Result Execution time Memory
48520 2018-05-15T12:45:49 Z Kmcode Boat (APIO16_boat) C++14
9 / 100
 926 ms 18860 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);
			if (up >= MOD)up %= MOD;
			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:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
boat.cpp:92:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vv.size(); j++) {
                   ~~~~~~^~~~~~~~~~~
boat.cpp:94: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 892 ms 18168 KB Output is correct
2 Correct 926 ms 18416 KB Output is correct
3 Correct 884 ms 18416 KB Output is correct
4 Correct 888 ms 18452 KB Output is correct
5 Correct 892 ms 18452 KB Output is correct
6 Correct 629 ms 18828 KB Output is correct
7 Correct 626 ms 18828 KB Output is correct
8 Correct 626 ms 18828 KB Output is correct
9 Correct 615 ms 18828 KB Output is correct
10 Correct 627 ms 18828 KB Output is correct
11 Correct 647 ms 18836 KB Output is correct
12 Correct 635 ms 18836 KB Output is correct
13 Correct 631 ms 18860 KB Output is correct
14 Correct 645 ms 18860 KB Output is correct
15 Correct 632 ms 18860 KB Output is correct
16 Correct 170 ms 18860 KB Output is correct
17 Correct 202 ms 18860 KB Output is correct
18 Correct 172 ms 18860 KB Output is correct
19 Correct 181 ms 18860 KB Output is correct
20 Correct 178 ms 18860 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 892 ms 18168 KB Output is correct
2 Correct 926 ms 18416 KB Output is correct
3 Correct 884 ms 18416 KB Output is correct
4 Correct 888 ms 18452 KB Output is correct
5 Correct 892 ms 18452 KB Output is correct
6 Correct 629 ms 18828 KB Output is correct
7 Correct 626 ms 18828 KB Output is correct
8 Correct 626 ms 18828 KB Output is correct
9 Correct 615 ms 18828 KB Output is correct
10 Correct 627 ms 18828 KB Output is correct
11 Correct 647 ms 18836 KB Output is correct
12 Correct 635 ms 18836 KB Output is correct
13 Correct 631 ms 18860 KB Output is correct
14 Correct 645 ms 18860 KB Output is correct
15 Correct 632 ms 18860 KB Output is correct
16 Correct 170 ms 18860 KB Output is correct
17 Correct 202 ms 18860 KB Output is correct
18 Correct 172 ms 18860 KB Output is correct
19 Correct 181 ms 18860 KB Output is correct
20 Correct 178 ms 18860 KB Output is correct
21 Incorrect 840 ms 18860 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 892 ms 18168 KB Output is correct
2 Correct 926 ms 18416 KB Output is correct
3 Correct 884 ms 18416 KB Output is correct
4 Correct 888 ms 18452 KB Output is correct
5 Correct 892 ms 18452 KB Output is correct
6 Correct 629 ms 18828 KB Output is correct
7 Correct 626 ms 18828 KB Output is correct
8 Correct 626 ms 18828 KB Output is correct
9 Correct 615 ms 18828 KB Output is correct
10 Correct 627 ms 18828 KB Output is correct
11 Correct 647 ms 18836 KB Output is correct
12 Correct 635 ms 18836 KB Output is correct
13 Correct 631 ms 18860 KB Output is correct
14 Correct 645 ms 18860 KB Output is correct
15 Correct 632 ms 18860 KB Output is correct
16 Correct 170 ms 18860 KB Output is correct
17 Correct 202 ms 18860 KB Output is correct
18 Correct 172 ms 18860 KB Output is correct
19 Correct 181 ms 18860 KB Output is correct
20 Correct 178 ms 18860 KB Output is correct
21 Incorrect 840 ms 18860 KB Output isn't correct
22 Halted 0 ms 0 KB -