Submission #1164297

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;

int N;
int D[100000];
int key[100000];
int dp[5][100000]; // choose a, under i

int main() {
    cin >> N;
    rep(i, N) cin >> D[i];
    sort(&D[0], &D[N]);

    int k1 = 0;
    rep(i, N){
        while(D[k1] * 2 <= D[i]){
            k1++;
        }
        key[i] = k1 - 1;
    }

    rep(i, N){
        dp[1][i] = i + 1;
    }

    for(int a = 2 ; a <=4; a++){
        rep(i, N){
            dp[a][i] = (key[i] != -1 ? dp[a-1][key[i]] : 0) + (i != 0 ? dp[a][i-1] : 0 );
            dp[a][i] %= 1000000007;
        }
    }

    cout << dp[4][N-1] << endl;

}

Submission Info

Judge Result