Submission #640291

#	Time	Username	Problem	Language	Result	Execution time	Memory
640291		sumit_kk10	Discharging (NOI20_discharging)	C++17	0 / 100	1062 ms	18520 KiB

Discharging

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int long long
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
int n, a[N], dp[N], p[N];

void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= n; ++i){
        int mx = 0;
        dp[i] = LLONG_MAX;
        for(int j = i; j >= 1; --j){
            mx = max(mx, a[j]);
            if(dp[j - 1] + ((p[j - 1] + mx) * (i - j + 1)) < dp[i]){
                dp[i] = dp[j - 1] + (p[j - 1] + mx) * (i - j + 1);
                p[i] = mx;
            }
        }
    }
    cout << dp[n] << "\n";
}

int32_t main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

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