oj.uz

Submission #2408

# Submission time Handle Problem Language Result Execution time Memory
2408 2013-07-21T08:57:45 Z pl0892029 지우개 (GA4_eraser) C++
0 / 100
 28 ms 2060 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

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

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 i=1;i<=n;i++)
        printf("%d ",val[i]);
        
    puts("");
    
    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
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 2060 KB Output isn't correct
2 Halted 0 ms 0 KB -