Submission #2433

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
2433	2013-07-21 11:02:51	pl0892029	지우개 (GA4_eraser)	C++98	100 / 100	25 ms	2056 KiB

eraser

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 26 / 26
• Subtask 6: 28 / 28