oj.uz

Submission #2433

# Submission time Handle Problem Language Result Execution time Memory
2433 2013-07-21T11:02:51 Z pl0892029 지우개 (GA4_eraser) C++
100 / 100
 25 ms 2056 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

int dp[100001], val[100001], sum[100001];
const int mod = 1000000007;

int main() {
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
        scanf("%d",val+i);
    
    for(int i=0;i<=n;i++) {
        sum[i] = 1;
    }
    sort(val+1,val+1+n);
    
    for(int p=0;p<3;p++) {
        int pivot = 0;
        for(int i=1;i<=n;i++) {
            while(pivot<i && val[pivot]<val[i]) pivot++;
            pivot--;
            dp[i] = (int)((long long)sum[pivot]*val[i]%mod);
        }
        sum[0] = 0;
        for(int i=1;i<=n;i++)
            sum[i] = (sum[i-1]+dp[i])%mod;
    }
    printf("%d",sum[n]);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2056 KB Output is correct
2 Correct 0 ms 2056 KB Output is correct
3 Correct 0 ms 2056 KB Output is correct
4 Correct 0 ms 2056 KB Output is correct
5 Correct 0 ms 2056 KB Output is correct
6 Correct 0 ms 2056 KB Output is correct
7 Correct 0 ms 2056 KB Output is correct
8 Correct 0 ms 2056 KB Output is correct
9 Correct 0 ms 2056 KB Output is correct
10 Correct 0 ms 2056 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2056 KB Output is correct
2 Correct 0 ms 2056 KB Output is correct
3 Correct 0 ms 2056 KB Output is correct
4 Correct 0 ms 2056 KB Output is correct
5 Correct 0 ms 2056 KB Output is correct
6 Correct 0 ms 2056 KB Output is correct
7 Correct 0 ms 2056 KB Output is correct
8 Correct 0 ms 2056 KB Output is correct
9 Correct 0 ms 2056 KB Output is correct
10 Correct 0 ms 2056 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2056 KB Output is correct
2 Correct 0 ms 2056 KB Output is correct
3 Correct 0 ms 2056 KB Output is correct
4 Correct 0 ms 2056 KB Output is correct
5 Correct 0 ms 2056 KB Output is correct
6 Correct 0 ms 2056 KB Output is correct
7 Correct 0 ms 2056 KB Output is correct
8 Correct 0 ms 2056 KB Output is correct
9 Correct 0 ms 2056 KB Output is correct
10 Correct 0 ms 2056 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2056 KB Output is correct
2 Correct 0 ms 2056 KB Output is correct
3 Correct 0 ms 2056 KB Output is correct
4 Correct 0 ms 2056 KB Output is correct
5 Correct 0 ms 2056 KB Output is correct
6 Correct 0 ms 2056 KB Output is correct
7 Correct 0 ms 2056 KB Output is correct
8 Correct 0 ms 2056 KB Output is correct
9 Correct 0 ms 2056 KB Output is correct
10 Correct 0 ms 2056 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2056 KB Output is correct
2 Correct 3 ms 2056 KB Output is correct
3 Correct 2 ms 2056 KB Output is correct
4 Correct 17 ms 2056 KB Output is correct
5 Correct 0 ms 2056 KB Output is correct
6 Correct 16 ms 2056 KB Output is correct
7 Correct 7 ms 2056 KB Output is correct
8 Correct 25 ms 2056 KB Output is correct
9 Correct 14 ms 2056 KB Output is correct
10 Correct 22 ms 2056 KB Output is correct

Subtask #6
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2056 KB Output is correct
2 Correct 0 ms 2056 KB Output is correct
3 Correct 23 ms 2056 KB Output is correct
4 Correct 4 ms 2056 KB Output is correct
5 Correct 23 ms 2056 KB Output is correct
6 Correct 4 ms 2056 KB Output is correct
7 Correct 18 ms 2056 KB Output is correct
8 Correct 21 ms 2056 KB Output is correct
9 Correct 24 ms 2056 KB Output is correct
10 Correct 16 ms 2056 KB Output is correct