Submission #471764

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> d(n);
	int i = 0;
	while ( i < n) {
		int val;
		cin >> val;
		d[i++] = val;
	}
	sort(d.begin(), d.end());
	vector<int> dist(n, n);
	for (int i = 0; i < n - 1; ++i) {
		int val = d[i];
		auto ret = lower_bound(vector<int>::iterator(&d[i + 1]), d.end(), 2 * val);
		if (ret != d.end()) 
		   dist[i] = ret - d.begin();
	        else
		   break;	
	}
	vector<vector<int>> res(n, vector<int>(3));
	for (int i = n - 1; i >= 0 ; --i) {
		if (dist[i] < n) 
			res[i][0] = n - dist[i];
		int count_1 = 0;
		int count_2 = 0;
		int count_3 = 0;
		for (int j = dist[i]; j < n; ++j) {
		     count_1 =  (count_1 + res[j][0]) % 1000000007;
		     count_2 =  (count_2 + res[j][1]) % 1000000007;
		}
		res[i][1] = count_1;
		if (i != n - 1) 
		    count_2 = (count_2 + res[i + 1][2]) % 1000000007;
		res[i][2] = count_2;
	}
	cout << res[0][2] << endl;
	return 0;
#if 0
	int count = 0;
	for (int i = 0; i < n - 3; ++i) {
		for (int j = dist[i]; j < n - 2; ++j)
			for (int k = dist[j]; k < n - 1; ++k) 
				for (int l = dist[k]; l < n; ++l) {
					count++;
					if (count == 1000000007) 
						count = 0;
				}	
	}
	cout << count << endl;
#endif
	return 0;
}

Submission Info

Judge Result