제출 #285582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285582		Ronin13	Discharging (NOI20_discharging)	C++14	36 / 100	16 ms	14080 KiB

Discharging

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define mp make_pair
 
using namespace std;
int n;
int m;
ll a[1501];
ll mx[1501][1501];
ll dp[1501];
bool check1(){
	for(int i=2;i<=n;i++)if(a[i]<a[i-1])return false;
	return true;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	if(check1()){
		for(int i=1;i<=n;i++){
    	dp[i]=LLONG_MAX;
    	for(int j=1;j<=i;j++){
    		dp[i]=min(dp[i],dp[j-1]+a[i]*(n-j+1));
		}
		
	}
	cout<<dp[n];
	return 0;
	}
	
	for(int i=1;i<=n;i++){
		ll mxx=-1;
		for(int j=i;j<=n;j++){
			mxx=max(a[j],mxx);
			mx[i][j]=mxx;
		
		}

	}
    for(int i=1;i<=n;i++){
    	dp[i]=LLONG_MAX;
    	for(int j=1;j<=i;j++){
    		dp[i]=min(dp[i],dp[j-1]+mx[j][i]*(n-j+1));
		}
	}
	cout<<dp[n];
	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