Submission #584964

#	Time	Username	Problem	Language	Result	Execution time	Memory
584964		mosiashvililuka	Discharging (NOI20_discharging)	C++14	36 / 100	1080 ms	18144 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
const long long N=999999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[1000009],dp[1000009];
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    for(i=1; i<=a; i++){
        cin>>f[i];
    }
    for(i=a; i>=1; i--){
        dp[i]=N;
        c=f[i];
        for(j=i; j<=a; j++){
            c=max(c,f[j]);
            dp[i]=min(dp[i],dp[j+1]+c*(a-i+1));
        }
    }
    cout<<dp[1];
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 14 / 14
• Subtask 6: 0 / 28