Submission #2433

#	Time	Username	Problem	Language	Result	Execution time	Memory
2433		pl0892029	지우개 (GA4_eraser)	C++98	100 / 100	25 ms	2056 KiB

eraser

#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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 26 / 26
• Subtask 6: 28 / 28