Submission #680293

#	Time	Username	Problem	Language	Result	Execution time	Memory
680293		stevancv	Discharging (NOI20_discharging)	C++14	100 / 100	356 ms	88384 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];
struct Line {
    ll a, b;
    Line() {
        a = b = 1e18;
    }
    Line(ll aa, ll bb) {
        a = aa; b = bb;
    }
    ll F(int x) {
        if (a == 1e18 && b == 1e18) return 1e18;
        return a * x + b;
    }

}st[4 * N];
void Add(int node, int l, int r, Line lin) {
    int mid = l + r >> 1;
    bool le = lin.F(l) < st[node].F(l);
    bool m = lin.F(mid) < st[node].F(mid);
    if (m) swap(st[node], lin);
    if (l == r) return;
    if (le != m) Add(2 * node, l, mid, lin);
    else Add(2 * node + 1, mid + 1, r, lin);
}
ll Get(int node, int l, int r, int x) {
    ll ans = st[node].F(x);
    if (l == r) return ans;
    int mid = l + r >> 1;
    if (x <= mid) smin(ans, Get(2 * node, l, mid, x));
    else smin(ans, Get(2 * node + 1, mid + 1, r, x));
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= 4 * n; i++) st[i] = Line();
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        smax(a[i], a[i - 1]);
        dp[i] = a[i] * n;
    }
    ll ans = 1e18;
    for (int i = n; i >= 1; i--) {
        ll o = Get(1, 1, n, i);
        if (o != 1e18) dp[i] += o;
        Add(1, 1, n, Line(-a[i], dp[i]));
        smin(ans, dp[i]);
    }
    cout << ans << en;
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'void Add(int, int, int, Line)':
Discharging.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
Discharging.cpp: In function 'long long int Get(int, int, int, int)':
Discharging.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l + r >> 1;
      |               ~~^~~

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