Submission #285022

#	Time	Username	Problem	Language	Result	Execution time	Memory
285022		keta_tsimakuridze	Discharging (NOI20_discharging)	C++14	47 / 100	1089 ms	8440 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[1000006],mx,dp[1505],F;
int main(){
	cin>>n;
	a[0]=1e10;
	for(k=1;k<=n;k++){
		cin>>a[k];
		if(a[k]>a[k-1]) F=1;
	}
	
	if(!F) cout<<a[1]*n;else{
	for(k=1;k<=n;k++){
		dp[k]=1e16;
		mx=0;
		for(int i=k;i>=1;i--){
			mx=max(mx,a[i]);
			dp[k]=min(dp[k],dp[i-1]+(n-i+1)*mx);
		}
	}
	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