답안 #48533 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48533	2018-05-15T13:08:19 Z	Kmcode	Boat (APIO16_boat)	C++14	9 / 100	2000 ms	18892 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;
			if (tmp < 0LL)while (1);
		}
	}
	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++;
					if (su < 0LL)while(1);
					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:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
boat.cpp:93:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vv.size(); j++) {
                   ~~~~~~^~~~~~~~~~~
boat.cpp:95: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	719 ms	18168 KB	Output is correct
2	Correct	714 ms	18328 KB	Output is correct
3	Correct	703 ms	18348 KB	Output is correct
4	Correct	707 ms	18416 KB	Output is correct
5	Correct	707 ms	18428 KB	Output is correct
6	Correct	606 ms	18860 KB	Output is correct
7	Correct	611 ms	18860 KB	Output is correct
8	Correct	629 ms	18860 KB	Output is correct
9	Correct	616 ms	18860 KB	Output is correct
10	Correct	608 ms	18860 KB	Output is correct
11	Correct	628 ms	18860 KB	Output is correct
12	Correct	617 ms	18860 KB	Output is correct
13	Correct	610 ms	18860 KB	Output is correct
14	Correct	667 ms	18892 KB	Output is correct
15	Correct	607 ms	18892 KB	Output is correct
16	Correct	156 ms	18892 KB	Output is correct
17	Correct	165 ms	18892 KB	Output is correct
18	Correct	163 ms	18892 KB	Output is correct
19	Correct	168 ms	18892 KB	Output is correct
20	Correct	162 ms	18892 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	719 ms	18168 KB	Output is correct
2	Correct	714 ms	18328 KB	Output is correct
3	Correct	703 ms	18348 KB	Output is correct
4	Correct	707 ms	18416 KB	Output is correct
5	Correct	707 ms	18428 KB	Output is correct
6	Correct	606 ms	18860 KB	Output is correct
7	Correct	611 ms	18860 KB	Output is correct
8	Correct	629 ms	18860 KB	Output is correct
9	Correct	616 ms	18860 KB	Output is correct
10	Correct	608 ms	18860 KB	Output is correct
11	Correct	628 ms	18860 KB	Output is correct
12	Correct	617 ms	18860 KB	Output is correct
13	Correct	610 ms	18860 KB	Output is correct
14	Correct	667 ms	18892 KB	Output is correct
15	Correct	607 ms	18892 KB	Output is correct
16	Correct	156 ms	18892 KB	Output is correct
17	Correct	165 ms	18892 KB	Output is correct
18	Correct	163 ms	18892 KB	Output is correct
19	Correct	168 ms	18892 KB	Output is correct
20	Correct	162 ms	18892 KB	Output is correct
21	Execution timed out	2076 ms	18892 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2081 ms	18892 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	719 ms	18168 KB	Output is correct
2	Correct	714 ms	18328 KB	Output is correct
3	Correct	703 ms	18348 KB	Output is correct
4	Correct	707 ms	18416 KB	Output is correct
5	Correct	707 ms	18428 KB	Output is correct
6	Correct	606 ms	18860 KB	Output is correct
7	Correct	611 ms	18860 KB	Output is correct
8	Correct	629 ms	18860 KB	Output is correct
9	Correct	616 ms	18860 KB	Output is correct
10	Correct	608 ms	18860 KB	Output is correct
11	Correct	628 ms	18860 KB	Output is correct
12	Correct	617 ms	18860 KB	Output is correct
13	Correct	610 ms	18860 KB	Output is correct
14	Correct	667 ms	18892 KB	Output is correct
15	Correct	607 ms	18892 KB	Output is correct
16	Correct	156 ms	18892 KB	Output is correct
17	Correct	165 ms	18892 KB	Output is correct
18	Correct	163 ms	18892 KB	Output is correct
19	Correct	168 ms	18892 KB	Output is correct
20	Correct	162 ms	18892 KB	Output is correct
21	Execution timed out	2076 ms	18892 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #48533

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