Submission #25185

#	Time	Username	Problem	Language	Result	Execution time	Memory
25185		gabrielsimoes	Boat (APIO16_boat)	C++14	0 / 100	9 ms	2048 KiB

boat

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1000000007;
const int MAXN = 501;
const int MAX = 1e6+10;

#define mod(a, b) ((a*b) % MOD)

ll invpow(ll a, ll b = MOD-2) {
	ll ret = 1;
	ll prod = a;
	for (int i = 0; i <= 30; i++) {
		if ((1LL << i) & a) ret = (ret * prod) % MOD;
		prod = (prod*prod) % MOD;
	}
	return ret;
}		

int n;
ll a[MAXN], b[MAXN];
vector<ll> v;

ll inv[MAXN];
ll bin[MAXN], c[MAXN];
ll dp[MAXN];

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld %lld", &a[i], &b[i]);
		b[i]++;
		v.push_back(a[i]);
		v.push_back(b[i]);
	}
	
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	
	for (int i = 1; i <= n; i++)
		inv[i] = invpow(i);
	
	for (int i = 0; i < n; i++) {
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
		b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
	}
	
	for (int i = 0; i < n; i++) dp[i] = 1;

	for (int region = 1; region < v.size(); region++) {
		ll L = v[region] - v[region-1];
		
		bin[0] = 1;
		for (int i = 1; i <= n; i++)
			bin[i] = i <= L ? mod(mod(L - i + 1, inv[i]), bin[i-1])
							: 0;

		c[1] = L;
		for (int i = 2; i <= n; i++)
			c[i] = (bin[i] + c[i-1] * (i-2)) % MOD;
		
		for (int i = n-1; i >= 0; i--) {
			if (region < a[i] || region > b[i]) continue;
			dp[i] += c[1] * (i > 0 ? dp[i-1] : 1);
			
			for (int k = i-1; k >= 0; k--) {
				if (region < a[k] || region > b[k]) continue;
				dp[i] += mod(c[i - k + 1], (k > 0 ? dp[k-1] : 1));
			}
			
			dp[i] %= MOD;
		}
	}
	
	ll ans = -1;
	for (int i = 0; i < n; i++)
		ans += dp[i] - 1;
	printf("%lld\n", ((ans%MOD) + MOD) % MOD);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:52:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int region = 1; region < v.size(); region++) {
                              ^
boat.cpp:31:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
boat.cpp:33:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &a[i], &b[i]);
                                   ^

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