Submission #1156047

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

ll dp[5][100010];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<ll> d(n);
	for (int i = 0; i < n; i++) cin >> d[i];
	sort(d.begin(), d.end());
	for (int i = 0; i < n; i++) dp[0][i] = 1;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < 4; j++) (dp[j][i] += dp[j][i + 1]) %= MOD;
		int idx = lower_bound(d.begin(), d.end(), d[i] * 2) - d.begin();
		if (idx == n) continue;
		for (int j = 3; j > 0; j--) {
			(dp[j][i] += dp[j - 1][idx]) %= MOD;
		}
	}
	cout << dp[3][0] << endl;
	return 0;
}

Submission Info

Judge Result