oj.uz

Submission #832858

# Submission time Handle Problem Language Result Execution time Memory
832858 2023-08-21T16:02:13 Z caganyanmaz Boat (APIO16_boat) C++17
58 / 100
 2000 ms 30268 KB 
#include <bits/stdc++.h>
#define int int64_t
#define pb push_back
using namespace std;


//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int MXN = 6000;
constexpr static int MXR = 11000;
int n;
vector<int> a, b;
vector<int> ranges;
int dp[MXR][MXN]; // Schools passed, last range, count in  last range
int old_dp[MXR][MXN];
int sums[MXN][MXN]; // last range
constexpr static int MOD = 1e9 + 7;

static inline int add(int a, int b) { return (a+b) % MOD; }
static inline int mul(int64_t a, int64_t b) { return (a*b) % MOD; }

int pow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b&1)
		{
			res = mul(a, res);
			b--;
		}
		else
		{
			a = mul(a, a);
			b >>= 1;
		}
	}
	return res;
}

int _div(int a, int b) { return mul(a, pow(b, MOD-2)); }
int C[MXR][MXN];
int p[MXN];

int32_t main()
{
	cin >> n;
	p[0] = 1;
	for (int i = 1; i < n; i++)
		p[i] = mul(i, p[i-1]);
	a.resize(n, 0), b.resize(n, 0);
	debug("A");
	for (int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
		b[i]++;
	}
	debug("b");
	vector<int> c;
 	for (int i = 0; i < n; i++)
		c.pb(a[i]);
	for (int i = 0; i < n; i++)
		c.pb(b[i]);
	debug("A");
	sort(c.begin(), c.end());
	auto last = unique(c.begin(), c.end());
	c.erase(last, c.end());
	int rn = c.size();
	for (int i = 0; i < c.size()-1; i++)
		ranges.pb(c[i+1] - c[i]);
	debug("B");
	for (int i = 0; i < rn; i++)
	{
		int pf = 1;
		for (int j = 0; j <= n; j++)
		{
			C[i][j] = pf;
			pf = mul(pf, ranges[i]-j);
			pf = _div(pf, j+1);
			if (ranges[i] < j)
				C[i][j] = 0;
			debug(i, j, C[i][j]);
		}
	}
	debug("D");
	debug(a, b);
	for (int& i : a)
		i = lower_bound(c.begin(), c.end(), i) - c.begin();
	for (int& i : b)
		i = lower_bound(c.begin(), c.end(), i) - c.begin();
	debug(a, b);
	for (int j = 0; j < rn; j++)
		old_dp[j][0] = 1;
	for (int i = 1; i <= n; i++) // Current node
	{
		for (int j = 0; j < rn; j++) // Current range
		{
			dp[j][0] = 1;
			for (int k = 1; k <= n; k++) // Current count 
			{
				dp[j][k] = 0;
				if (a[i-1] <= j && b[i-1] > j)
				{
					if (j > 0 && k == 1)
						dp[j][k] = add(dp[j][k], sums[i-1][j-1]); // Starting with it
					dp[j][k] = add(dp[j][k], old_dp[j][k-1]); // Including it		
					debug(i, j, k);
				}
				dp[j][k] = add(dp[j][k], old_dp[j][k]); // Not including it
				debug(i, j, k, dp[j][k]);
			}
		}
		for (int j = 0; j < rn; j++)
		{
			if (j > 0)
				sums[i][j] = add(sums[i][j], sums[i][j-1]);
			debug(sums[i][j]);
			for (int k = 1; k <= n; k++)
			{
				sums[i][j] = add(sums[i][j], mul(dp[j][k], C[j][k]));
			}
			debug(i, j, sums[i][j]);
		}
		for (int j = 0; j < rn; j++)
			for (int k = 1; k <= n; k++)
				old_dp[j][k] = dp[j][k];
	}
	int res = 0;
	for (int i = 0; i < rn; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			debug(i, j, old_dp[i][j]);
			res = add(res, mul(old_dp[i][j], C[i][j]));
		}
	
	}
	cout << res << "\n";
}

Compilation message

boat.cpp: In function 'int32_t main()':
boat.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for (int i = 0; i < c.size()-1; i++)
      |                  ~~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1788 ms 30128 KB Output is correct
2 Correct 1736 ms 30064 KB Output is correct
3 Correct 1746 ms 30088 KB Output is correct
4 Correct 1740 ms 30088 KB Output is correct
5 Correct 1749 ms 30132 KB Output is correct
6 Correct 1725 ms 30176 KB Output is correct
7 Correct 1723 ms 30268 KB Output is correct
8 Correct 1741 ms 30228 KB Output is correct
9 Correct 1763 ms 30128 KB Output is correct
10 Correct 1728 ms 30212 KB Output is correct
11 Correct 1774 ms 30244 KB Output is correct
12 Correct 1735 ms 30056 KB Output is correct
13 Correct 1685 ms 30084 KB Output is correct
14 Correct 1725 ms 30132 KB Output is correct
15 Correct 1741 ms 30112 KB Output is correct
16 Correct 275 ms 7200 KB Output is correct
17 Correct 291 ms 7608 KB Output is correct
18 Correct 275 ms 7372 KB Output is correct
19 Correct 306 ms 7672 KB Output is correct
20 Correct 281 ms 7372 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1788 ms 30128 KB Output is correct
2 Correct 1736 ms 30064 KB Output is correct
3 Correct 1746 ms 30088 KB Output is correct
4 Correct 1740 ms 30088 KB Output is correct
5 Correct 1749 ms 30132 KB Output is correct
6 Correct 1725 ms 30176 KB Output is correct
7 Correct 1723 ms 30268 KB Output is correct
8 Correct 1741 ms 30228 KB Output is correct
9 Correct 1763 ms 30128 KB Output is correct
10 Correct 1728 ms 30212 KB Output is correct
11 Correct 1774 ms 30244 KB Output is correct
12 Correct 1735 ms 30056 KB Output is correct
13 Correct 1685 ms 30084 KB Output is correct
14 Correct 1725 ms 30132 KB Output is correct
15 Correct 1741 ms 30112 KB Output is correct
16 Correct 275 ms 7200 KB Output is correct
17 Correct 291 ms 7608 KB Output is correct
18 Correct 275 ms 7372 KB Output is correct
19 Correct 306 ms 7672 KB Output is correct
20 Correct 281 ms 7372 KB Output is correct
21 Correct 1653 ms 27660 KB Output is correct
22 Correct 1664 ms 28040 KB Output is correct
23 Correct 1692 ms 27608 KB Output is correct
24 Correct 1655 ms 27404 KB Output is correct
25 Correct 1635 ms 27640 KB Output is correct
26 Correct 1635 ms 26856 KB Output is correct
27 Correct 1694 ms 27172 KB Output is correct
28 Correct 1623 ms 26780 KB Output is correct
29 Correct 1634 ms 26736 KB Output is correct
30 Correct 1760 ms 30128 KB Output is correct
31 Correct 1688 ms 30144 KB Output is correct
32 Correct 1768 ms 30116 KB Output is correct
33 Correct 1745 ms 30044 KB Output is correct
34 Correct 1746 ms 30064 KB Output is correct
35 Correct 1704 ms 30116 KB Output is correct
36 Correct 1734 ms 29992 KB Output is correct
37 Correct 1737 ms 30056 KB Output is correct
38 Correct 1829 ms 30040 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3796 KB Output is correct
2 Correct 18 ms 3732 KB Output is correct
3 Correct 17 ms 3784 KB Output is correct
4 Correct 17 ms 3772 KB Output is correct
5 Correct 22 ms 3712 KB Output is correct
6 Correct 18 ms 3768 KB Output is correct
7 Correct 18 ms 3796 KB Output is correct
8 Correct 23 ms 3696 KB Output is correct
9 Correct 22 ms 3728 KB Output is correct
10 Correct 18 ms 3688 KB Output is correct
11 Correct 17 ms 3788 KB Output is correct
12 Correct 17 ms 3788 KB Output is correct
13 Correct 17 ms 3696 KB Output is correct
14 Correct 22 ms 3716 KB Output is correct
15 Correct 18 ms 3760 KB Output is correct
16 Correct 10 ms 2464 KB Output is correct
17 Correct 10 ms 2360 KB Output is correct
18 Correct 10 ms 2388 KB Output is correct
19 Correct 10 ms 2388 KB Output is correct
20 Correct 10 ms 2340 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1788 ms 30128 KB Output is correct
2 Correct 1736 ms 30064 KB Output is correct
3 Correct 1746 ms 30088 KB Output is correct
4 Correct 1740 ms 30088 KB Output is correct
5 Correct 1749 ms 30132 KB Output is correct
6 Correct 1725 ms 30176 KB Output is correct
7 Correct 1723 ms 30268 KB Output is correct
8 Correct 1741 ms 30228 KB Output is correct
9 Correct 1763 ms 30128 KB Output is correct
10 Correct 1728 ms 30212 KB Output is correct
11 Correct 1774 ms 30244 KB Output is correct
12 Correct 1735 ms 30056 KB Output is correct
13 Correct 1685 ms 30084 KB Output is correct
14 Correct 1725 ms 30132 KB Output is correct
15 Correct 1741 ms 30112 KB Output is correct
16 Correct 275 ms 7200 KB Output is correct
17 Correct 291 ms 7608 KB Output is correct
18 Correct 275 ms 7372 KB Output is correct
19 Correct 306 ms 7672 KB Output is correct
20 Correct 281 ms 7372 KB Output is correct
21 Correct 1653 ms 27660 KB Output is correct
22 Correct 1664 ms 28040 KB Output is correct
23 Correct 1692 ms 27608 KB Output is correct
24 Correct 1655 ms 27404 KB Output is correct
25 Correct 1635 ms 27640 KB Output is correct
26 Correct 1635 ms 26856 KB Output is correct
27 Correct 1694 ms 27172 KB Output is correct
28 Correct 1623 ms 26780 KB Output is correct
29 Correct 1634 ms 26736 KB Output is correct
30 Correct 1760 ms 30128 KB Output is correct
31 Correct 1688 ms 30144 KB Output is correct
32 Correct 1768 ms 30116 KB Output is correct
33 Correct 1745 ms 30044 KB Output is correct
34 Correct 1746 ms 30064 KB Output is correct
35 Correct 1704 ms 30116 KB Output is correct
36 Correct 1734 ms 29992 KB Output is correct
37 Correct 1737 ms 30056 KB Output is correct
38 Correct 1829 ms 30040 KB Output is correct
39 Correct 17 ms 3796 KB Output is correct
40 Correct 18 ms 3732 KB Output is correct
41 Correct 17 ms 3784 KB Output is correct
42 Correct 17 ms 3772 KB Output is correct
43 Correct 22 ms 3712 KB Output is correct
44 Correct 18 ms 3768 KB Output is correct
45 Correct 18 ms 3796 KB Output is correct
46 Correct 23 ms 3696 KB Output is correct
47 Correct 22 ms 3728 KB Output is correct
48 Correct 18 ms 3688 KB Output is correct
49 Correct 17 ms 3788 KB Output is correct
50 Correct 17 ms 3788 KB Output is correct
51 Correct 17 ms 3696 KB Output is correct
52 Correct 22 ms 3716 KB Output is correct
53 Correct 18 ms 3760 KB Output is correct
54 Correct 10 ms 2464 KB Output is correct
55 Correct 10 ms 2360 KB Output is correct
56 Correct 10 ms 2388 KB Output is correct
57 Correct 10 ms 2388 KB Output is correct
58 Correct 10 ms 2340 KB Output is correct
59 Correct 1905 ms 30064 KB Output is correct
60 Correct 1860 ms 30136 KB Output is correct
61 Correct 1970 ms 30144 KB Output is correct
62 Correct 1989 ms 30140 KB Output is correct
63 Correct 1976 ms 30092 KB Output is correct
64 Execution timed out 2061 ms 30220 KB Time limit exceeded
65 Halted 0 ms 0 KB -