oj.uz

Submission #111379

# Submission time Handle Problem Language Result Execution time Memory
111379 2019-05-15T04:13:53 Z diamond_duke Boat (APIO16_boat) C++11
9 / 100
 494 ms 4380 KB 
#include <algorithm>
#include <cstring>
#include <cstdio>
using ll = long long;
constexpr int MOD = 1e9 + 7;
inline int quick_pow(int a, int n)
{
	int res = 1;
	while (n)
	{
		if (n & 1)
			res = (ll)res * a % MOD;
		a = (ll)a * a % MOD;
		n >>= 1;
	}
	return res;
}
int lp[505], rp[505], app[1005], dp[1005][505], sum[1005][505], inv[505];
int main()
{
	// freopen("uoj-204.in", "r", stdin);
	int n, cnt = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", lp + i, rp + i);
		app[cnt++] = lp[i];
		app[cnt++] = ++rp[i];
	}
	std::sort(app, app + cnt);
	cnt = std::unique(app, app + cnt) - app;
	for (int i = 0; i < n; i++)
	{
		lp[i] = std::lower_bound(app, app + cnt, lp[i]) - app;
		rp[i] = std::lower_bound(app, app + cnt, rp[i]) - app;
	}
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= n; i++)
		inv[i] = (ll)(MOD - MOD / i) * inv[MOD % i] % MOD;
	dp[0][0] = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < cnt; j++)
		{
			for (int k = 0; k <= i; k++)
				sum[j + 1][k] = (sum[j][k] + dp[j][k]) % MOD;
		}
		for (int j = lp[i]; j < rp[i]; j++)
		{
			int len = app[j + 1] - app[j];
			for (int k = i; k >= 0; k--)
			{
				dp[j][k + 1] = (dp[j][k + 1] + (ll)dp[j][k] * (len - k) % MOD * inv[k + 1]) % MOD;
				dp[j][1] = (dp[j][1] + (ll)sum[j][k] * len) % MOD;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < cnt; i++)
	{
		for (int j = 0; j <= n; j++)
			ans = (ans + dp[i][j]) % MOD;
	}
	printf("%d\n", (ans + MOD - 1) % MOD);
	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
boat.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", lp + i, rp + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 4344 KB Output is correct
2 Correct 270 ms 4216 KB Output is correct
3 Correct 244 ms 4264 KB Output is correct
4 Correct 272 ms 4340 KB Output is correct
5 Correct 254 ms 4316 KB Output is correct
6 Correct 250 ms 4320 KB Output is correct
7 Correct 366 ms 4316 KB Output is correct
8 Correct 296 ms 4332 KB Output is correct
9 Correct 248 ms 4312 KB Output is correct
10 Correct 216 ms 4216 KB Output is correct
11 Correct 235 ms 4324 KB Output is correct
12 Correct 216 ms 4380 KB Output is correct
13 Correct 248 ms 4344 KB Output is correct
14 Correct 230 ms 4344 KB Output is correct
15 Correct 253 ms 4360 KB Output is correct
16 Correct 53 ms 1024 KB Output is correct
17 Correct 67 ms 1144 KB Output is correct
18 Correct 47 ms 1024 KB Output is correct
19 Correct 59 ms 1144 KB Output is correct
20 Correct 46 ms 1144 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 4344 KB Output is correct
2 Correct 270 ms 4216 KB Output is correct
3 Correct 244 ms 4264 KB Output is correct
4 Correct 272 ms 4340 KB Output is correct
5 Correct 254 ms 4316 KB Output is correct
6 Correct 250 ms 4320 KB Output is correct
7 Correct 366 ms 4316 KB Output is correct
8 Correct 296 ms 4332 KB Output is correct
9 Correct 248 ms 4312 KB Output is correct
10 Correct 216 ms 4216 KB Output is correct
11 Correct 235 ms 4324 KB Output is correct
12 Correct 216 ms 4380 KB Output is correct
13 Correct 248 ms 4344 KB Output is correct
14 Correct 230 ms 4344 KB Output is correct
15 Correct 253 ms 4360 KB Output is correct
16 Correct 53 ms 1024 KB Output is correct
17 Correct 67 ms 1144 KB Output is correct
18 Correct 47 ms 1024 KB Output is correct
19 Correct 59 ms 1144 KB Output is correct
20 Correct 46 ms 1144 KB Output is correct
21 Incorrect 494 ms 3960 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 4344 KB Output is correct
2 Correct 270 ms 4216 KB Output is correct
3 Correct 244 ms 4264 KB Output is correct
4 Correct 272 ms 4340 KB Output is correct
5 Correct 254 ms 4316 KB Output is correct
6 Correct 250 ms 4320 KB Output is correct
7 Correct 366 ms 4316 KB Output is correct
8 Correct 296 ms 4332 KB Output is correct
9 Correct 248 ms 4312 KB Output is correct
10 Correct 216 ms 4216 KB Output is correct
11 Correct 235 ms 4324 KB Output is correct
12 Correct 216 ms 4380 KB Output is correct
13 Correct 248 ms 4344 KB Output is correct
14 Correct 230 ms 4344 KB Output is correct
15 Correct 253 ms 4360 KB Output is correct
16 Correct 53 ms 1024 KB Output is correct
17 Correct 67 ms 1144 KB Output is correct
18 Correct 47 ms 1024 KB Output is correct
19 Correct 59 ms 1144 KB Output is correct
20 Correct 46 ms 1144 KB Output is correct
21 Incorrect 494 ms 3960 KB Output isn't correct
22 Halted 0 ms 0 KB -