Submission #832878

#	Time	Username	Problem	Language	Result	Execution time	Memory
832878		caganyanmaz	Boat (APIO16_boat)	C++17	100 / 100	1864 ms	43680 KiB

boat

#include <bits/stdc++.h>


#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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 = 1000;
constexpr static int MXR = 2000;
int n;
vector<int> a, b;
vector<int> ranges;
vector<vector<int>> dp(MXR, vector<int>(MXN, 0)); // Schools passed, last range, count in  last range
vector<vector<int>> old_dp(MXR, vector<int>(MXN, 0));
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; }

static inline 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;
}

static inline 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]);
		}
		swap(old_dp, dp);
	}
	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 (stderr)

boat.cpp: In function 'int32_t main()':
boat.cpp:78: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]
   78 |  for (int i = 0; i < c.size()-1; i++)
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42