답안 #40748 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40748	2018-02-08T02:41:38 Z	ssnsarang2023	Boat (APIO16_boat)	C++14	36 / 100	101 ms	2668 KB

boat

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;

#define SZ(x) ((int)x.size())

const int mod = (int)1e9+7;

int fast_pw(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % mod; 
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return res;
}

const int N = 505;
int n, f[N], g[N], ftmp[N], a[N], b[N], inv[N], tmp[N], m;
int choose[N][N], len[N], lenCk[N][N], c1[N];
vector<int> c;

void add(int &x, int y) {
	x += y, x %= mod;
	if (x < 0) x += mod;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", &a[i], &b[i]);
		++b[i];
		c.push_back(a[i]);
		c.push_back(b[i]);
	}
	sort(c.begin(), c.end());
	c.resize(distance(c.begin(), unique(c.begin(), c.end())));
	for (int i = 0; i <= n; ++i) choose[i][i] = choose[i][0] = 1;
	inv[0] = f[0] = g[0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j < i; ++j)
			choose[i][j] = (choose[i - 1][j - 1] + choose[i - 1][j]) % mod;
		inv[i] = fast_pw(i, mod - 2);
		g[i] = 1;
	}
	int sz = 0;
	for (int i = 0; i < SZ(c) - 1; ++i) {
		len[++sz] = c[i + 1] - c[i];
		lenCk[sz][0] = 1;
		for (int j = 1; j <= min(len[sz], n); ++j) {
			lenCk[sz][j] = 1ll * lenCk[sz][j - 1] * (len[sz] - j + 1) % mod;
			lenCk[sz][j] = 1ll * lenCk[sz][j] * inv[j] % mod;
		}
	}
	for (int i = 1; i <= sz; ++i) {
		m = 0;
		for (int j = 1; j <= n; ++j)
			if (a[j] <= c[i - 1] && c[i] <= b[j])
				tmp[++m] = j;
		for (int j = 1; j <= m; ++j) {
			int id = tmp[j];
			if (j == 1) {
				for (int k = 0; k <= m; ++k) c1[k] = 0;
				c1[1] = lenCk[i][1];
				for (int k = 2; k <= m; ++k)
					for (int x = 2; x <= min(k, len[i]); ++x)
						add(c1[k], 1ll * lenCk[i][x] * choose[k - 2][x - 2] % mod);
			}
			for (int k = j; k <= m; ++k) {
				int mid = k - j + 1, id2 = tmp[k];
				add(ftmp[id2], 1ll * c1[mid] * g[id - 1] % mod);
			}
		}
		g[0] = 1;
		for (int j = 1; j <= n; ++j) {
			add(f[j], ftmp[j]);
			g[j] = (g[j - 1] + f[j]) % mod;
			ftmp[j] = 0;
		}
	}
	printf("%d", (g[n] - 1 + mod) % mod);
	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:34:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
boat.cpp:36:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i], &b[i]);
                              ^

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2296 KB	Output is correct
2	Correct	11 ms	2400 KB	Output is correct
3	Correct	12 ms	2400 KB	Output is correct
4	Correct	11 ms	2400 KB	Output is correct
5	Correct	12 ms	2596 KB	Output is correct
6	Correct	11 ms	2596 KB	Output is correct
7	Correct	10 ms	2664 KB	Output is correct
8	Correct	10 ms	2664 KB	Output is correct
9	Correct	10 ms	2668 KB	Output is correct
10	Correct	10 ms	2668 KB	Output is correct
11	Correct	10 ms	2668 KB	Output is correct
12	Correct	10 ms	2668 KB	Output is correct
13	Correct	10 ms	2668 KB	Output is correct
14	Correct	11 ms	2668 KB	Output is correct
15	Correct	10 ms	2668 KB	Output is correct
16	Correct	4 ms	2668 KB	Output is correct
17	Correct	4 ms	2668 KB	Output is correct
18	Correct	4 ms	2668 KB	Output is correct
19	Correct	4 ms	2668 KB	Output is correct
20	Correct	4 ms	2668 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2296 KB	Output is correct
2	Correct	11 ms	2400 KB	Output is correct
3	Correct	12 ms	2400 KB	Output is correct
4	Correct	11 ms	2400 KB	Output is correct
5	Correct	12 ms	2596 KB	Output is correct
6	Correct	11 ms	2596 KB	Output is correct
7	Correct	10 ms	2664 KB	Output is correct
8	Correct	10 ms	2664 KB	Output is correct
9	Correct	10 ms	2668 KB	Output is correct
10	Correct	10 ms	2668 KB	Output is correct
11	Correct	10 ms	2668 KB	Output is correct
12	Correct	10 ms	2668 KB	Output is correct
13	Correct	10 ms	2668 KB	Output is correct
14	Correct	11 ms	2668 KB	Output is correct
15	Correct	10 ms	2668 KB	Output is correct
16	Correct	4 ms	2668 KB	Output is correct
17	Correct	4 ms	2668 KB	Output is correct
18	Correct	4 ms	2668 KB	Output is correct
19	Correct	4 ms	2668 KB	Output is correct
20	Correct	4 ms	2668 KB	Output is correct
21	Incorrect	101 ms	2668 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2668 KB	Output is correct
2	Correct	3 ms	2668 KB	Output is correct
3	Correct	4 ms	2668 KB	Output is correct
4	Correct	4 ms	2668 KB	Output is correct
5	Correct	4 ms	2668 KB	Output is correct
6	Correct	6 ms	2668 KB	Output is correct
7	Correct	7 ms	2668 KB	Output is correct
8	Correct	7 ms	2668 KB	Output is correct
9	Correct	6 ms	2668 KB	Output is correct
10	Correct	6 ms	2668 KB	Output is correct
11	Correct	5 ms	2668 KB	Output is correct
12	Correct	3 ms	2668 KB	Output is correct
13	Correct	4 ms	2668 KB	Output is correct
14	Correct	4 ms	2668 KB	Output is correct
15	Correct	4 ms	2668 KB	Output is correct
16	Correct	3 ms	2668 KB	Output is correct
17	Correct	3 ms	2668 KB	Output is correct
18	Correct	3 ms	2668 KB	Output is correct
19	Correct	3 ms	2668 KB	Output is correct
20	Correct	3 ms	2668 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2296 KB	Output is correct
2	Correct	11 ms	2400 KB	Output is correct
3	Correct	12 ms	2400 KB	Output is correct
4	Correct	11 ms	2400 KB	Output is correct
5	Correct	12 ms	2596 KB	Output is correct
6	Correct	11 ms	2596 KB	Output is correct
7	Correct	10 ms	2664 KB	Output is correct
8	Correct	10 ms	2664 KB	Output is correct
9	Correct	10 ms	2668 KB	Output is correct
10	Correct	10 ms	2668 KB	Output is correct
11	Correct	10 ms	2668 KB	Output is correct
12	Correct	10 ms	2668 KB	Output is correct
13	Correct	10 ms	2668 KB	Output is correct
14	Correct	11 ms	2668 KB	Output is correct
15	Correct	10 ms	2668 KB	Output is correct
16	Correct	4 ms	2668 KB	Output is correct
17	Correct	4 ms	2668 KB	Output is correct
18	Correct	4 ms	2668 KB	Output is correct
19	Correct	4 ms	2668 KB	Output is correct
20	Correct	4 ms	2668 KB	Output is correct
21	Incorrect	101 ms	2668 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #40748

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 42.0