Submission #1170033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170033		altern23	Discharging (NOI20_discharging)	C++20	36 / 100	1094 ms	15944 KiB

Discharging

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll MAXN = 2e5;
const ll INF = 4e18;
const ll MOD = 998244353;

struct line{
    ll m, c;
};

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll N; cin >> N;
        vector<ll> a(N + 5), dp(N + 5, INF);
        for(int i = 1; i <= N; i++) cin >> a[i];

        dp[0] = 0;
        ll MX = -1;
        for(int i = 1; i <= N; i++){
            MX = max(MX, a[i]);
            for(int j = i - 1; j >= 0; --j){
                dp[i] = min(dp[i], dp[j] + (N - j) * MX);
            }
        }

        cout << dp[N] << "\n";
    }   
}

/*
dp[i] = max(dp[i], dp[j] + (n - j) * a[i])
*/

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