Submission #1354323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354323		Faisal_Saqib	Discharging (NOI20_discharging)	C++20	36 / 100	1 ms	344 KiB

Discharging

#include <iostream>
using namespace std;
typedef long long ll;
const int N=2000;
ll a[N];
ll dp[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[n+1-i],dp[i]=1e18;
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        ll mx=0;
        for(int j=i+1;j<=n;j++)
        {
            mx=max(mx,a[j]);
            dp[j]=min(dp[j],dp[i]+1ll*mx*j);
        }
    }
    cout<<dp[n]<<endl;
}

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