Submission #637734

#	Time	Username	Problem	Language	Result	Execution time	Memory
637734		lovrot	Boat (APIO16_boat)	C++11	100 / 100	1303 ms	25532 KiB

boat

#include <bits/stdc++.h> 

#define ll long long
#define pii pair<ll, ll> 
#define X first
#define Y second
#define pb push_back

using namespace std; 

const int N = 1010;
const ll MOD = 1e9 + 7;

ll n, intcnt, l[N], r[N];
ll siz[N], fact[N], povrh[N][N], inv[N];
ll dp[N][N], calc[N][N];

int u[N][N];

vector<pii> intv;
vector<ll> v;

ll add(ll a, ll b){ 
	return (a + b >= MOD ? a + b - MOD : a + b);
}

ll mult(ll a, ll b){ 
	return a * b % MOD;
}

ll fastpow(ll b, ll e){ 
	ll ret = 1;
	while(e){
		if(e & 1) ret = mult(ret, b);
		b = mult(b, b);
		e >>= 1;
	}
	return ret;
}

ll divd(ll a, ll b){ 
	return mult(a, fastpow(b, MOD - 2));
}

void precompute(){ 
	fact[0] = 1;
	for(int i = 1; i < N; i++){ 
		fact[i] = mult(fact[i - 1], i);
		inv[i] = fastpow(fact[i], MOD - 2);
	}

	for(int i = 0; i < N; i++){ 
		for(int j = 0; j <= i; j++){ 
			if(j == 0 || j == i) povrh[i][j] = 1;
			else povrh[i][j] = add(povrh[i - 1][j - 1], povrh[i - 1][j]);
		}
	}
	
	for(int i = 0; i < intcnt; i++){
		for(ll k = 1; k <= n; k++){ 
			ll sfact = 1;
			for(ll j = 1; j <= k; j++){ 
				sfact = mult(sfact, siz[i] - j + 1);
				calc[i][k] = add(calc[i][k], mult(povrh[k - 1][j - 1], mult(sfact, inv[j])));
			}
		}
	}
}

ll DP(int x, int b){ 
	if(b >= intcnt) return 1;
	if(dp[x][b] != -1) return dp[x][b];

	dp[x][b] = DP(x, b + 1);

	int cnt = 0;
	for(int i = x; i < n; i++){ 
		cnt += u[i][b];
		if(u[i][b]) dp[x][b] = add(dp[x][b], mult(calc[b][cnt], DP(i + 1, b + 1)));
	}

	return dp[x][b];
}

int main(){ 
	for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) dp[i][j] = -1;

	scanf("%lld", &n);

	for(int i = 0; i < n; i++){ 
		scanf("%lld%lld", &l[i], &r[i]);
		v.pb(l[i]);
		v.pb(r[i] + 1);
	}

	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());

	for(int i = 0; i < v.size() - 1; i++){ 
		intv.pb({v[i], v[i + 1] - 1});
	}

	intcnt = intv.size();
 
	for(int i = 0; i < intcnt; i++) siz[i] = intv[i].Y - intv[i].X + 1;

	for(int i = 0; i < n; i++){
		for(ll j = 0; j < intcnt; j++){ 
			if(intv[j].X >= l[i] && intv[j].Y <= r[i]){ 
				u[i][j] = true;
			}
		}
	}

	precompute();
	
	printf("%lld\n", add(DP(0, 0), MOD - 1));
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i = 0; i < v.size() - 1; i++){
      |                 ~~^~~~~~~~~~~~~~
boat.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
boat.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%lld%lld", &l[i], &r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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