oj.uz

Submission #111376

# Submission time Handle Problem Language Result Execution time Memory
111376 2019-05-15T04:05:36 Z diamond_duke Boat (APIO16_boat) C++11
27 / 100
 242 ms 4472 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[205], dp[2][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][0] = 1;
	for (int i = 0; i < n; i++)
	{
		auto cur = dp[i & 1], nxt = dp[i & 1 ^ 1];
		memcpy(nxt, cur, sizeof(dp[i & 1]));
		for (int j = 0; j < cnt; j++)
		{
			for (int k = 0; k <= i; k++)
			{
				if (!cur[j][k])
					continue;
				for (int x = std::max(j, lp[i]); x < rp[i]; x++)
				{
					int t = (x == j) * k + 1, len = app[x + 1] - app[x];
					nxt[x][t] = (nxt[x][t] + (ll)cur[j][k] * (len - t + 1) % MOD * inv[t]) % MOD;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < cnt; i++)
	{
		for (int j = 0; j <= n; j++)
			ans = (ans + dp[n & 1][i][j]) % MOD;
	}
	printf("%d\n", (ans + MOD - 1) % MOD);
	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:43:36: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   auto cur = dp[i & 1], nxt = dp[i & 1 ^ 1];
                                  ~~^~~
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
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 4324 KB Output is correct
2 Correct 63 ms 4352 KB Output is correct
3 Correct 85 ms 4352 KB Output is correct
4 Correct 76 ms 4224 KB Output is correct
5 Correct 85 ms 4352 KB Output is correct
6 Correct 194 ms 4224 KB Output is correct
7 Correct 224 ms 4472 KB Output is correct
8 Correct 189 ms 4324 KB Output is correct
9 Correct 194 ms 4224 KB Output is correct
10 Correct 242 ms 4352 KB Output is correct
11 Correct 133 ms 4472 KB Output is correct
12 Correct 134 ms 4320 KB Output is correct
13 Correct 98 ms 4316 KB Output is correct
14 Correct 95 ms 4352 KB Output is correct
15 Correct 124 ms 4320 KB Output is correct
16 Correct 46 ms 4352 KB Output is correct
17 Correct 50 ms 4352 KB Output is correct
18 Correct 42 ms 4224 KB Output is correct
19 Correct 40 ms 4224 KB Output is correct
20 Correct 49 ms 4252 KB Output is correct

Subtask #4
0 / 42.0

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