oj.uz

Submission #25198

# Submission time Handle Problem Language Result Execution time Memory
25198 2017-06-20T17:31:02 Z gabrielsimoes Boat (APIO16_boat) C++14
9 / 100
 113 ms 2052 KB 
#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) & b)
			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], sum[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 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] * ll(i-2)) % MOD;
			
		sum[0] = 1;
		for (int i = 1; i <= n; i++)
			sum[i] = (dp[i-1] + sum[i-1]) % MOD;
		
		for (int i = n-1; i >= 0; i--) {
			if (region <= a[i] || region > b[i]) continue;
			
			for (int k = i; k >= 0; k--) {
				if (region <= a[k] || region > b[k]) continue;
				dp[i] += mod(c[i - k + 1], sum[k]);
			}
			
			dp[i] %= MOD;
		}
	}
	
	ll ans = 0;
	for (int i = 0; i < n; i++)
		ans += dp[i];
	printf("%lld\n", ans % MOD);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:51:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int region = 1; region < v.size(); region++) {
                              ^
boat.cpp:32:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
boat.cpp:34: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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2052 KB Output is correct
2 Correct 13 ms 2052 KB Output is correct
3 Correct 13 ms 2052 KB Output is correct
4 Correct 13 ms 2052 KB Output is correct
5 Correct 13 ms 2052 KB Output is correct
6 Correct 9 ms 2052 KB Output is correct
7 Correct 9 ms 2052 KB Output is correct
8 Correct 13 ms 2052 KB Output is correct
9 Correct 9 ms 2052 KB Output is correct
10 Correct 9 ms 2052 KB Output is correct
11 Correct 9 ms 2052 KB Output is correct
12 Correct 9 ms 2052 KB Output is correct
13 Correct 9 ms 2052 KB Output is correct
14 Correct 13 ms 2052 KB Output is correct
15 Correct 9 ms 2052 KB Output is correct
16 Correct 3 ms 2052 KB Output is correct
17 Correct 3 ms 2052 KB Output is correct
18 Correct 3 ms 2052 KB Output is correct
19 Correct 3 ms 2052 KB Output is correct
20 Correct 3 ms 2052 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2052 KB Output is correct
2 Correct 13 ms 2052 KB Output is correct
3 Correct 13 ms 2052 KB Output is correct
4 Correct 13 ms 2052 KB Output is correct
5 Correct 13 ms 2052 KB Output is correct
6 Correct 9 ms 2052 KB Output is correct
7 Correct 9 ms 2052 KB Output is correct
8 Correct 13 ms 2052 KB Output is correct
9 Correct 9 ms 2052 KB Output is correct
10 Correct 9 ms 2052 KB Output is correct
11 Correct 9 ms 2052 KB Output is correct
12 Correct 9 ms 2052 KB Output is correct
13 Correct 9 ms 2052 KB Output is correct
14 Correct 13 ms 2052 KB Output is correct
15 Correct 9 ms 2052 KB Output is correct
16 Correct 3 ms 2052 KB Output is correct
17 Correct 3 ms 2052 KB Output is correct
18 Correct 3 ms 2052 KB Output is correct
19 Correct 3 ms 2052 KB Output is correct
20 Correct 3 ms 2052 KB Output is correct
21 Incorrect 113 ms 2052 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2052 KB Output is correct
2 Correct 13 ms 2052 KB Output is correct
3 Correct 13 ms 2052 KB Output is correct
4 Correct 13 ms 2052 KB Output is correct
5 Correct 13 ms 2052 KB Output is correct
6 Correct 9 ms 2052 KB Output is correct
7 Correct 9 ms 2052 KB Output is correct
8 Correct 13 ms 2052 KB Output is correct
9 Correct 9 ms 2052 KB Output is correct
10 Correct 9 ms 2052 KB Output is correct
11 Correct 9 ms 2052 KB Output is correct
12 Correct 9 ms 2052 KB Output is correct
13 Correct 9 ms 2052 KB Output is correct
14 Correct 13 ms 2052 KB Output is correct
15 Correct 9 ms 2052 KB Output is correct
16 Correct 3 ms 2052 KB Output is correct
17 Correct 3 ms 2052 KB Output is correct
18 Correct 3 ms 2052 KB Output is correct
19 Correct 3 ms 2052 KB Output is correct
20 Correct 3 ms 2052 KB Output is correct
21 Incorrect 113 ms 2052 KB Output isn't correct
22 Halted 0 ms 0 KB -