답안 #48527 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48527	2018-05-15T13:04:09 Z	Kmcode	Boat (APIO16_boat)	C++14	9 / 100	866 ms	18940 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++;
					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	849 ms	18168 KB	Output is correct
2	Correct	841 ms	18532 KB	Output is correct
3	Correct	856 ms	18532 KB	Output is correct
4	Correct	866 ms	18532 KB	Output is correct
5	Correct	840 ms	18532 KB	Output is correct
6	Correct	597 ms	18592 KB	Output is correct
7	Correct	599 ms	18596 KB	Output is correct
8	Correct	606 ms	18720 KB	Output is correct
9	Correct	621 ms	18796 KB	Output is correct
10	Correct	613 ms	18796 KB	Output is correct
11	Correct	612 ms	18800 KB	Output is correct
12	Correct	612 ms	18800 KB	Output is correct
13	Correct	611 ms	18800 KB	Output is correct
14	Correct	612 ms	18940 KB	Output is correct
15	Correct	603 ms	18940 KB	Output is correct
16	Correct	170 ms	18940 KB	Output is correct
17	Correct	179 ms	18940 KB	Output is correct
18	Correct	172 ms	18940 KB	Output is correct
19	Correct	177 ms	18940 KB	Output is correct
20	Correct	178 ms	18940 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	849 ms	18168 KB	Output is correct
2	Correct	841 ms	18532 KB	Output is correct
3	Correct	856 ms	18532 KB	Output is correct
4	Correct	866 ms	18532 KB	Output is correct
5	Correct	840 ms	18532 KB	Output is correct
6	Correct	597 ms	18592 KB	Output is correct
7	Correct	599 ms	18596 KB	Output is correct
8	Correct	606 ms	18720 KB	Output is correct
9	Correct	621 ms	18796 KB	Output is correct
10	Correct	613 ms	18796 KB	Output is correct
11	Correct	612 ms	18800 KB	Output is correct
12	Correct	612 ms	18800 KB	Output is correct
13	Correct	611 ms	18800 KB	Output is correct
14	Correct	612 ms	18940 KB	Output is correct
15	Correct	603 ms	18940 KB	Output is correct
16	Correct	170 ms	18940 KB	Output is correct
17	Correct	179 ms	18940 KB	Output is correct
18	Correct	172 ms	18940 KB	Output is correct
19	Correct	177 ms	18940 KB	Output is correct
20	Correct	178 ms	18940 KB	Output is correct
21	Runtime error	815 ms	18940 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	161 ms	18940 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	849 ms	18168 KB	Output is correct
2	Correct	841 ms	18532 KB	Output is correct
3	Correct	856 ms	18532 KB	Output is correct
4	Correct	866 ms	18532 KB	Output is correct
5	Correct	840 ms	18532 KB	Output is correct
6	Correct	597 ms	18592 KB	Output is correct
7	Correct	599 ms	18596 KB	Output is correct
8	Correct	606 ms	18720 KB	Output is correct
9	Correct	621 ms	18796 KB	Output is correct
10	Correct	613 ms	18796 KB	Output is correct
11	Correct	612 ms	18800 KB	Output is correct
12	Correct	612 ms	18800 KB	Output is correct
13	Correct	611 ms	18800 KB	Output is correct
14	Correct	612 ms	18940 KB	Output is correct
15	Correct	603 ms	18940 KB	Output is correct
16	Correct	170 ms	18940 KB	Output is correct
17	Correct	179 ms	18940 KB	Output is correct
18	Correct	172 ms	18940 KB	Output is correct
19	Correct	177 ms	18940 KB	Output is correct
20	Correct	178 ms	18940 KB	Output is correct
21	Runtime error	815 ms	18940 KB	Execution failed because the return code was nonzero
22	Halted	0 ms	0 KB	-

답안 #48527

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