結果

提出番号	1890
提出者	nxteru
言語	C++
提出日時	2018-08-04 14:24:50
問題名	(71)音楽ゲーム
結果	WA
点数	0%

---

テストケース

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
ll n,a[100005],dp[100005],h[100005];
int main(void){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    a[n]=1000000000;
    dp[0]=1;
    for(int i=0;i<n;i++){
        dp[i]=(dp[i]+h[i])%M;
        int u=upper_bound(a,a+n+1,a[i])-a;
        h[u]=(h[u]+dp[i])%M;
        h[i+1]=(h[i]+h[i+1])%M;
    }
    cout<<(dp[n]+h[n])%M<<endl;
}