結果

提出番号	1709
提出者	nebukuro09
言語	C++
提出日時	2018-08-04 13:35:33
問題名	(71)音楽ゲーム
結果	WA
点数	0%

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;
typedef long double ld;

const ll MOD = 1000000007;
ll A[101010];
ll dp[101010];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    REP(i, N) cin >> A[i];
    sort(A, A+N);

    ll tmp = 0;
    int last = -1;

    REP(i, N) {
        if (i == 0) {
            dp[i] = 1;
            continue;
        }
        while (last + 1 < N && A[last + 1] < A[i]) {
            ++last;
            (tmp += dp[last]) %= MOD;
        }
        (dp[i] += tmp) %= MOD;
    }

    ll ans = 0;
    REP(i, N) ans = (ans + dp[i]) % MOD;
    cout << ans << endl;
}