oj.uz

Submission #111377

# Submission time Handle Problem Language Result Execution time Memory
111377 2019-05-15T04:06:06 Z diamond_duke Boat (APIO16_boat) C++11
36 / 100
 2000 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[1005], 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 4472 KB Output is correct
2 Correct 208 ms 4224 KB Output is correct
3 Correct 210 ms 4344 KB Output is correct
4 Correct 214 ms 4472 KB Output is correct
5 Correct 209 ms 4224 KB Output is correct
6 Correct 213 ms 4352 KB Output is correct
7 Correct 209 ms 4324 KB Output is correct
8 Correct 203 ms 4472 KB Output is correct
9 Correct 191 ms 4352 KB Output is correct
10 Correct 224 ms 4352 KB Output is correct
11 Correct 217 ms 4352 KB Output is correct
12 Correct 197 ms 4352 KB Output is correct
13 Correct 192 ms 4352 KB Output is correct
14 Correct 219 ms 4328 KB Output is correct
15 Correct 207 ms 4472 KB Output is correct
16 Correct 116 ms 4224 KB Output is correct
17 Correct 129 ms 4352 KB Output is correct
18 Correct 117 ms 4316 KB Output is correct
19 Correct 122 ms 4224 KB Output is correct
20 Correct 108 ms 4224 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 4472 KB Output is correct
2 Correct 208 ms 4224 KB Output is correct
3 Correct 210 ms 4344 KB Output is correct
4 Correct 214 ms 4472 KB Output is correct
5 Correct 209 ms 4224 KB Output is correct
6 Correct 213 ms 4352 KB Output is correct
7 Correct 209 ms 4324 KB Output is correct
8 Correct 203 ms 4472 KB Output is correct
9 Correct 191 ms 4352 KB Output is correct
10 Correct 224 ms 4352 KB Output is correct
11 Correct 217 ms 4352 KB Output is correct
12 Correct 197 ms 4352 KB Output is correct
13 Correct 192 ms 4352 KB Output is correct
14 Correct 219 ms 4328 KB Output is correct
15 Correct 207 ms 4472 KB Output is correct
16 Correct 116 ms 4224 KB Output is correct
17 Correct 129 ms 4352 KB Output is correct
18 Correct 117 ms 4316 KB Output is correct
19 Correct 122 ms 4224 KB Output is correct
20 Correct 108 ms 4224 KB Output is correct
21 Execution timed out 2045 ms 4224 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 4320 KB Output is correct
2 Correct 70 ms 4320 KB Output is correct
3 Correct 92 ms 4352 KB Output is correct
4 Correct 89 ms 4224 KB Output is correct
5 Correct 89 ms 4320 KB Output is correct
6 Correct 235 ms 4224 KB Output is correct
7 Correct 224 ms 4352 KB Output is correct
8 Correct 223 ms 4352 KB Output is correct
9 Correct 208 ms 4344 KB Output is correct
10 Correct 326 ms 4224 KB Output is correct
11 Correct 111 ms 4224 KB Output is correct
12 Correct 105 ms 4352 KB Output is correct
13 Correct 95 ms 4344 KB Output is correct
14 Correct 95 ms 4352 KB Output is correct
15 Correct 124 ms 4320 KB Output is correct
16 Correct 49 ms 4344 KB Output is correct
17 Correct 39 ms 4352 KB Output is correct
18 Correct 46 ms 4472 KB Output is correct
19 Correct 47 ms 4352 KB Output is correct
20 Correct 43 ms 4352 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 4472 KB Output is correct
2 Correct 208 ms 4224 KB Output is correct
3 Correct 210 ms 4344 KB Output is correct
4 Correct 214 ms 4472 KB Output is correct
5 Correct 209 ms 4224 KB Output is correct
6 Correct 213 ms 4352 KB Output is correct
7 Correct 209 ms 4324 KB Output is correct
8 Correct 203 ms 4472 KB Output is correct
9 Correct 191 ms 4352 KB Output is correct
10 Correct 224 ms 4352 KB Output is correct
11 Correct 217 ms 4352 KB Output is correct
12 Correct 197 ms 4352 KB Output is correct
13 Correct 192 ms 4352 KB Output is correct
14 Correct 219 ms 4328 KB Output is correct
15 Correct 207 ms 4472 KB Output is correct
16 Correct 116 ms 4224 KB Output is correct
17 Correct 129 ms 4352 KB Output is correct
18 Correct 117 ms 4316 KB Output is correct
19 Correct 122 ms 4224 KB Output is correct
20 Correct 108 ms 4224 KB Output is correct
21 Execution timed out 2045 ms 4224 KB Time limit exceeded
22 Halted 0 ms 0 KB -