Submission #470897


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

const ll M = 1000000007;

int main(){
	static int n;
	static int d[100010];
	scanf("%d",&n);
	rep(i,n){
		scanf("%d",&d[i]);
	}
	
	vector<int> vec;
	rep(i,n)vec.pb(d[i]);
	sor(vec);
	
	static ll dp[100010][4] = {};
	rep(i,n){
		dp[i][0] = 1;
		if(i > 0)dp[i][0] += dp[i-1][0];
		int l = ub(vec,vec[i]/2) - vec.begin();
		l --;
		if(l >= 0){
			rep1(j,3){
				dp[i][j] = dp[l][j-1];
				if(i > 0)dp[i][j] += dp[i-1][j];
				dp[i][j] %= M;
			}
		}
		/*rep(j,4){
			printf("%lld ",dp[i][j]);
		}
		puts("");*/
	}
	
	cout << dp[n-1][3] << endl;
}
		

Submission Info

Submission Time
Task B - 難易度
User yokozuna57
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1590 Byte
Status
Exec Time 77 ms
Memory 4768 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:44:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&d[i]);
                    ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 50 / 50 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt
Subtask2 50 / 50 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt
Case Name Status Exec Time Memory
sample_01.txt 25 ms 804 KB
sample_02.txt 26 ms 924 KB
sample_03.txt 26 ms 800 KB
subtask1_01.txt 27 ms 924 KB
subtask1_02.txt 27 ms 924 KB
subtask1_03.txt 28 ms 924 KB
subtask1_04.txt 27 ms 924 KB
subtask1_05.txt 26 ms 928 KB
subtask1_06.txt 28 ms 876 KB
subtask1_07.txt 27 ms 812 KB
subtask1_08.txt 28 ms 928 KB
subtask1_09.txt 27 ms 1044 KB
subtask1_10.txt 27 ms 812 KB
subtask1_11.txt 27 ms 804 KB
subtask1_12.txt 27 ms 928 KB
subtask1_13.txt 24 ms 928 KB
subtask1_14.txt 25 ms 804 KB
subtask1_15.txt 26 ms 928 KB
subtask1_16.txt 24 ms 1052 KB
subtask1_17.txt 26 ms 924 KB
subtask1_18.txt 26 ms 920 KB
subtask1_19.txt 26 ms 1052 KB
subtask2_01.txt 37 ms 2084 KB
subtask2_02.txt 35 ms 1828 KB
subtask2_03.txt 28 ms 1436 KB
subtask2_04.txt 31 ms 1312 KB
subtask2_05.txt 59 ms 3996 KB
subtask2_06.txt 56 ms 3600 KB
subtask2_07.txt 28 ms 1048 KB
subtask2_08.txt 28 ms 1048 KB
subtask2_09.txt 77 ms 4160 KB
subtask2_10.txt 47 ms 2852 KB
subtask2_11.txt 28 ms 924 KB
subtask2_12.txt 46 ms 2724 KB
subtask2_13.txt 28 ms 1056 KB
subtask2_14.txt 52 ms 3232 KB
subtask2_15.txt 70 ms 4768 KB
subtask2_16.txt 72 ms 4760 KB
subtask2_17.txt 69 ms 4764 KB
subtask2_18.txt 69 ms 4756 KB
subtask2_19.txt 69 ms 4764 KB
subtask2_20.txt 53 ms 4764 KB
subtask2_21.txt 53 ms 4756 KB