Submission #22966

#	Time	Username	Problem	Language	Result	Execution time	Memory
22966		Bruteforceman	Boat (APIO16_boat)	C++11	100 / 100	976 ms	8500 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long Long;
typedef pair <int, int> pii;

const int mod = 1000000007;

Long bigmod(int x, int y) {
	if(y == 0) return 1;
	if(y & 1) return (bigmod(x, y-1) * x) % mod;
	Long m = bigmod(x, y >> 1);
	return (m * m) % mod; 
}
Long inv[505];
int a[505];
int b[505];
int n;

int cntG;
vector <int> g[1005];
int cost[1005];
int c[505][505];

bool overlap(int l, int r, int i) {
	if(a[i] <= l and r <= b[i]) return true;
	else return false;
}
bool veryBad(int l, int r, int i) {
	if(l <= a[i] and a[i] <= r) return true;
	if(l <= b[i] and b[i] <= r) return true;
	else return false;
}
void divideGroups() {
	vector <pii> v;
	for(int i = 1; i <= n; i++) {
		v.push_back(pii(a[i], 0));
		v.push_back(pii(b[i], 1));
	}
	sort(v.begin(), v.end());

	int prev = v.at(0).first;
	int now;
	for(int i = 1; i < (int) v.size(); i++) {
		pii x = v.at(i);
		if(x.second == 0) {
			now = x.first - 1;
		} else {
			now = x.first;
		}
		cost[i] = now - prev + 1;
		for(int j = 1; j <= n; j++) {
			if(prev > now) continue;
			if(overlap(prev, now, j)) {
				g[i].push_back(j);
			} else {
				assert(veryBad(prev, now, j) == false);
			}
		}
		prev = now + 1;
	}
	cntG = v.size() - 1;
}

int calc(int costx, int x) {
	Long sum = 0;
	Long nCr = 1;
	for(int i = 1; i <= x; i++) {
		if(i > costx) break;
		nCr *= (costx - i + 1);
		nCr %= mod;
		nCr *= inv[i];
		nCr %= mod;
		sum += c[x - 1][i - 1] * nCr;
		sum %= mod;		
	}
	return sum;
}

int fn[1005][505];
int gn[1005][505];

int dp(int group, int x) {
	if(group > cntG) return 1;
	if(fn[group][x] != -1) return fn[group][x];

	Long ans = dp(group + 1, x);
	int k = 0;
	for(int i : g[group]) {
		if(i < x) continue;
		++k;
		ans += 1LL * gn[group][k] * dp(group + 1, i + 1);
		ans %= mod;
	}
	return fn[group][x] = ans;
}
int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie (0);

	for(int i = 1; i <= 500; i++) {
		inv[i] = bigmod(i, mod - 2);
	}
	for(int i = 0; i <= 500; i++) c[i][0] = 1;
	for(int i = 1; i <= 500; i++) {
		for(int j = 1; j <= 500; j++) {
			c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
			c[i][j] %= mod;
		}
	} 
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
	}
	divideGroups();
	for(int i = 1; i <= cntG; i++) {
		int size = g[i].size();
		for(int j = 1; j <= size; j++) {
			gn[i][j] = calc(cost[i], j);
		}
	}
	
	memset(fn, -1, sizeof fn);
	int ans = dp(1, 1);
	ans -= 1;
	if(ans < 0) ans += mod;
	cout << ans << endl;
	return 0;
}

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