답안 #48519 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48519	2018-05-15T12:42:15 Z	Kmcode	Boat (APIO16_boat)	C++14	9 / 100	831 ms	18788 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);
			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:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
boat.cpp:91:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vv.size(); j++) {
                   ~~~~~~^~~~~~~~~~~
boat.cpp:93: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	711 ms	18364 KB	Output is correct
2	Correct	692 ms	18364 KB	Output is correct
3	Correct	682 ms	18460 KB	Output is correct
4	Correct	702 ms	18460 KB	Output is correct
5	Correct	707 ms	18536 KB	Output is correct
6	Correct	397 ms	18536 KB	Output is correct
7	Correct	384 ms	18744 KB	Output is correct
8	Correct	409 ms	18744 KB	Output is correct
9	Correct	400 ms	18784 KB	Output is correct
10	Correct	391 ms	18788 KB	Output is correct
11	Correct	412 ms	18788 KB	Output is correct
12	Correct	419 ms	18788 KB	Output is correct
13	Correct	411 ms	18788 KB	Output is correct
14	Correct	395 ms	18788 KB	Output is correct
15	Correct	399 ms	18788 KB	Output is correct
16	Correct	132 ms	18788 KB	Output is correct
17	Correct	137 ms	18788 KB	Output is correct
18	Correct	133 ms	18788 KB	Output is correct
19	Correct	140 ms	18788 KB	Output is correct
20	Correct	135 ms	18788 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	711 ms	18364 KB	Output is correct
2	Correct	692 ms	18364 KB	Output is correct
3	Correct	682 ms	18460 KB	Output is correct
4	Correct	702 ms	18460 KB	Output is correct
5	Correct	707 ms	18536 KB	Output is correct
6	Correct	397 ms	18536 KB	Output is correct
7	Correct	384 ms	18744 KB	Output is correct
8	Correct	409 ms	18744 KB	Output is correct
9	Correct	400 ms	18784 KB	Output is correct
10	Correct	391 ms	18788 KB	Output is correct
11	Correct	412 ms	18788 KB	Output is correct
12	Correct	419 ms	18788 KB	Output is correct
13	Correct	411 ms	18788 KB	Output is correct
14	Correct	395 ms	18788 KB	Output is correct
15	Correct	399 ms	18788 KB	Output is correct
16	Correct	132 ms	18788 KB	Output is correct
17	Correct	137 ms	18788 KB	Output is correct
18	Correct	133 ms	18788 KB	Output is correct
19	Correct	140 ms	18788 KB	Output is correct
20	Correct	135 ms	18788 KB	Output is correct
21	Incorrect	831 ms	18788 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	78 ms	18788 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	711 ms	18364 KB	Output is correct
2	Correct	692 ms	18364 KB	Output is correct
3	Correct	682 ms	18460 KB	Output is correct
4	Correct	702 ms	18460 KB	Output is correct
5	Correct	707 ms	18536 KB	Output is correct
6	Correct	397 ms	18536 KB	Output is correct
7	Correct	384 ms	18744 KB	Output is correct
8	Correct	409 ms	18744 KB	Output is correct
9	Correct	400 ms	18784 KB	Output is correct
10	Correct	391 ms	18788 KB	Output is correct
11	Correct	412 ms	18788 KB	Output is correct
12	Correct	419 ms	18788 KB	Output is correct
13	Correct	411 ms	18788 KB	Output is correct
14	Correct	395 ms	18788 KB	Output is correct
15	Correct	399 ms	18788 KB	Output is correct
16	Correct	132 ms	18788 KB	Output is correct
17	Correct	137 ms	18788 KB	Output is correct
18	Correct	133 ms	18788 KB	Output is correct
19	Correct	140 ms	18788 KB	Output is correct
20	Correct	135 ms	18788 KB	Output is correct
21	Incorrect	831 ms	18788 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #48519

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