Submission #1278640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278640		ducdev	Discharging (NOI20_discharging)	C++17	100 / 100	83 ms	27828 KiB

Discharging

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX_N = 1e6;
const int MOD = 1e9 + 7;

struct Line {
    ll a, b;

    Line() {};
    Line(ll a, ll b) : a(a), b(b) {};

    double intersect(const Line &other) const {
        return (double)(other.b - b) / (a - other.a);
    };

    ll eval(ll x) {
        return a * x + b;
    };
};

struct ConvexHullTrick {
    Line lines[MAX_N + 5];
    int ptr, sz;

    void addLine(const Line &newLine) {
        while (sz > 1 && lines[sz - 2].intersect(newLine) <= lines[sz - 2].intersect(lines[sz - 1])) sz--;
        lines[sz++] = newLine;
        if (ptr >= sz) ptr = max(0, sz - 1);
    };

    ll query(ll x) {
        while (ptr + 1 < sz && lines[ptr].eval(x) >= lines[ptr + 1].eval(x)) ptr++;
        return lines[ptr].eval(x);
    };

    void reset() { sz = ptr = 0; };
    ConvexHullTrick() { reset(); };
};

int n;
int a[MAX_N + 5];
ll dp[MAX_N + 5];
ConvexHullTrick cht;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    };

    ConvexHullTrick cht;

    int mx = 0;
    for (int i = 1; i <= n; i++) {
        cht.addLine(Line(-i, dp[i - 1]));
        if (a[i] > mx) {
            mx = a[i];
            dp[i] = cht.query(mx) + 1LL * mx * (n + 1);
        } else
            dp[i] = dp[i - 1];
    };

    cout << dp[n];
};

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("MAIN.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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