Submission #680279

#	Time	Username	Problem	Language	Result	Execution time	Memory
680279		stevancv	Discharging (NOI20_discharging)	C++14	36 / 100	1076 ms	18116 KiB

Discharging

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define sadd(a, b) a = Add(a, b)
#define smul(a, b) a = Mul(a, b)
using namespace std;
const int N = 1e6 + 2;
const int mod = 1e9 + 7;
ll a[N], dp[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        smax(a[i], a[i - 1]);
    }
    ll ans = 1e18;
    for (int i = n; i >= 1; i--) {
        ll o = 1e18;
        for (int j = i + 1; j <= n; j++) if (a[i] < a[j]) smin(o, dp[j] - a[j] * i);
        dp[i] = a[i] * n;
        if (o != 1e18) dp[i] += o;
        smin(ans, dp[i]);
    }
    cout << ans << en;
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:20:9: warning: unused variable 'mx' [-Wunused-variable]
   20 |     int mx = 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