Submission #2242899

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,a) for(int i=0;i<(a);i++)
#define MOD 1000000007

const int NMAX=100000;
ll dp[NMAX+10][4],sum[NMAX+10][4];
int D[NMAX+10];

int main(){
  int N; cin>>N;
  rep(i,N) cin>>D[i];
  D[N]=0;
  sort(D,D+N+1);
  ll ans=0;
  for(int i=1;i<=N;i++){
    int x=lower_bound(D,D+i+1,D[i]/2+1)-D;
    while(D[x]*2>D[i]) x--;
    dp[i][0]=1;
    dp[i][1]=sum[x][0];
    dp[i][2]=sum[x][1];
    dp[i][3]=sum[x][2];
    rep(j,3) sum[i][j]=(sum[i-1][j]+dp[i][j])%MOD;
    ans+=dp[i][3];
  }
  cout<<ans%MOD<<endl;
  return 0;
}

Submission Info

Judge Result