Submission #285003

#	Time	Username	Problem	Language	Result	Execution time	Memory
285003		wildturtle	Discharging (NOI20_discharging)	C++14	47 / 100	894 ms	12408 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,A[1000005],minn,maxx,dp[1000006];
int main() {
    cin>>n;
    for(long long i=1;i<=n;i++) {
        cin>>A[i];
    }
    if(n==1) { cout<<A[1]; return 0; }
    if(n==2) { cout<<min(A[1]+A[1]+A[2],2*max(A[1],A[2])); return 0; }
    if(n==3) { 
        a=A[1]+A[1]+A[2]+A[1]+A[2]+A[3];
        b=2*max(A[1],A[2])+max(A[1],A[2])+A[3];
        d=A[1]+2*(max(A[2],A[3])+A[1]);
        c=3*max(A[1],max(A[2],A[3]));
    cout<<min(min(a,b),min(c,d)); 
        return 0; 
    }
    if(n>1500) cout<<A[1]*n;
    else {
        for(long long i=1;i<=n;i++) {
            maxx=A[i];
            dp[i]=dp[i-1]+A[i]*(n-i+1);
            for(long long j=i-1;j>=1;j--) {
                maxx=max(maxx,A[j]);
                if(dp[j-1]+maxx*(n-j+1)<dp[i]) dp[i]=dp[j-1]+maxx*(n-j+1);
            }
           // cout<<dp[i]<<" ";
        }
        cout<<dp[n];
    }
}

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