Submission #1281497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281497		quangminh412	Discharging (NOI20_discharging)	C++17	100 / 100	90 ms	12320 KiB

Discharging

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const ll oo = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6 + 1;

struct MinHull
{
    struct Line
    {
        ll a, b;

        Line(ll a, ll b) : a(a), b(b) {};
        ll Calc(ll x) { return a * x + b; }
    };

    double intersect(Line l1, Line l2)
    {
        return 1.0 * (l1.b - l2.b) / (l2.a - l1.a);
    }
    double overlap(Line l1, Line l2, Line l3)
    {
        return intersect(l2, l3) < intersect(l1, l3);
    }

    vector<Line> L;
    vector<double> X;

    void add(ll a, ll b)
    {
        Line NewLine(a, b);

        while (L.size() >= 2 && overlap(L[L.size() - 2], L[L.size() - 1], NewLine))
        {
            L.pop_back();
            X.pop_back();
        }

        if (L.size())
            X.push_back(intersect(L.back(), NewLine));
        L.push_back(NewLine);
    }

    ll query(ll x)
    {
        int i = lower_bound(X.begin(), X.end(), x) - X.begin();
        return L[i].Calc(x);
    }
};

int t[maxn];
int n;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> t[i];

    int idx = 1, cursor = 1;
    vector<ll> dp(n + 1, 0);
    dp[1] = 1ll * t[1] * n;
    MinHull H;
    for (int i = 2; i <= n; i++)
    {
        if (t[i] >= t[idx])
            idx = i;
        while (cursor <= idx)
        {
            H.add(n - cursor + 1, dp[cursor - 1]);
            cursor++;
        }
        dp[i] = H.query(t[idx]);
    }

    cout << dp[n] << '\n';
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(), "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