Submission #793423

#	Time	Username	Problem	Language	Result	Execution time	Memory
793423		IvanJ	Boat (APIO16_boat)	C++17	100 / 100	443 ms	4324 KiB

boat

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1005;
const int MOD = 1e9 + 7;

int mult(ll a, ll b) {return (a * b) % MOD;}
int pot(int n, int k) {
	int ret = 1, pot = n;
	for(;k > 0;k >>= 1, pot = mult(pot, pot)) 
		if(k & 1) ret = mult(ret, pot);
	return ret;
}
int divide(int a, int b) {return mult(a, pot(b, MOD - 2));}
int add(int a, int b) {a += b;if(a >= MOD) a -= MOD;return a;}
int sub(int a, int b) {a -= b;if(a < 0) a += MOD;return a;}

int n, m;
int a[maxn], b[maxn];
int len[maxn], inv[maxn];
int dp[maxn][maxn];
vector<int> v;

int main() {
	scanf("%d", &n);
	for(int i = 1;i <= n;i++) 
		scanf("%d%d", a + i, b + i), b[i]++;
	
	for(int i = 1;i <= n;i++) 
		inv[i] = divide(1, i);

	for(int i = 1;i <= n;i++)
		v.pb(a[i]), v.pb(b[i]);
	sort(v.begin(), v.end());
	v.resize(unique(all(v)) - v.begin());
    
	for(int i = 1;i <= n;i++) {
		a[i] = lower_bound(all(v), a[i]) - v.begin() + 1;
		b[i] = lower_bound(all(v), b[i]) - v.begin() + 1;
	}
    
	m = (int)v.size() - 1;
	for(int i = 1;i <= m;i++) 
		len[i] = v[i] - v[i - 1];

	dp[0][0] = 1;
	for(int i = 1;i <= m;i++){
		dp[i][0] = 1;
		for(int j = 1;j <= n;j++){
			ll to_mul = len[i];
			int cnt = 1;
			dp[i][j] = dp[i - 1][j];
			if(i < a[j] || i >= b[j]) continue;
			
			for(int k = j - 1;k >= 0;k--) {
				dp[i][j] = add(dp[i][j], mult(dp[i - 1][k], to_mul));
				if(a[k] <= i && i < b[k]) {
					to_mul = mult(mult(to_mul, add(cnt, len[i])), inv[cnt + 1]);
					cnt++;
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i++) 
		ans = add(ans, dp[m][i]);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
boat.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   scanf("%d%d", a + i, b + i), b[i]++;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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