답안 #48525 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48525	2018-05-15T13:02:07 Z	Kmcode	Boat (APIO16_boat)	C++14	9 / 100	903 ms	18888 KB

boat

#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;
		}
	}
	if (AA < 0LL)exit(1);
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	883 ms	18256 KB	Output is correct
2	Correct	876 ms	18336 KB	Output is correct
3	Correct	866 ms	18460 KB	Output is correct
4	Correct	903 ms	18508 KB	Output is correct
5	Correct	891 ms	18508 KB	Output is correct
6	Correct	619 ms	18620 KB	Output is correct
7	Correct	622 ms	18888 KB	Output is correct
8	Correct	619 ms	18888 KB	Output is correct
9	Correct	630 ms	18888 KB	Output is correct
10	Correct	627 ms	18888 KB	Output is correct
11	Correct	624 ms	18888 KB	Output is correct
12	Correct	644 ms	18888 KB	Output is correct
13	Correct	650 ms	18888 KB	Output is correct
14	Correct	614 ms	18888 KB	Output is correct
15	Correct	626 ms	18888 KB	Output is correct
16	Correct	167 ms	18888 KB	Output is correct
17	Correct	181 ms	18888 KB	Output is correct
18	Correct	169 ms	18888 KB	Output is correct
19	Correct	182 ms	18888 KB	Output is correct
20	Correct	177 ms	18888 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	883 ms	18256 KB	Output is correct
2	Correct	876 ms	18336 KB	Output is correct
3	Correct	866 ms	18460 KB	Output is correct
4	Correct	903 ms	18508 KB	Output is correct
5	Correct	891 ms	18508 KB	Output is correct
6	Correct	619 ms	18620 KB	Output is correct
7	Correct	622 ms	18888 KB	Output is correct
8	Correct	619 ms	18888 KB	Output is correct
9	Correct	630 ms	18888 KB	Output is correct
10	Correct	627 ms	18888 KB	Output is correct
11	Correct	624 ms	18888 KB	Output is correct
12	Correct	644 ms	18888 KB	Output is correct
13	Correct	650 ms	18888 KB	Output is correct
14	Correct	614 ms	18888 KB	Output is correct
15	Correct	626 ms	18888 KB	Output is correct
16	Correct	167 ms	18888 KB	Output is correct
17	Correct	181 ms	18888 KB	Output is correct
18	Correct	169 ms	18888 KB	Output is correct
19	Correct	182 ms	18888 KB	Output is correct
20	Correct	177 ms	18888 KB	Output is correct
21	Runtime error	870 ms	18888 KB	Execution failed because the return code was nonzero
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	166 ms	18888 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	883 ms	18256 KB	Output is correct
2	Correct	876 ms	18336 KB	Output is correct
3	Correct	866 ms	18460 KB	Output is correct
4	Correct	903 ms	18508 KB	Output is correct
5	Correct	891 ms	18508 KB	Output is correct
6	Correct	619 ms	18620 KB	Output is correct
7	Correct	622 ms	18888 KB	Output is correct
8	Correct	619 ms	18888 KB	Output is correct
9	Correct	630 ms	18888 KB	Output is correct
10	Correct	627 ms	18888 KB	Output is correct
11	Correct	624 ms	18888 KB	Output is correct
12	Correct	644 ms	18888 KB	Output is correct
13	Correct	650 ms	18888 KB	Output is correct
14	Correct	614 ms	18888 KB	Output is correct
15	Correct	626 ms	18888 KB	Output is correct
16	Correct	167 ms	18888 KB	Output is correct
17	Correct	181 ms	18888 KB	Output is correct
18	Correct	169 ms	18888 KB	Output is correct
19	Correct	182 ms	18888 KB	Output is correct
20	Correct	177 ms	18888 KB	Output is correct
21	Runtime error	870 ms	18888 KB	Execution failed because the return code was nonzero
22	Halted	0 ms	0 KB	-

답안 #48525

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0