Submission #697506

#	Time	Username	Problem	Language	Result	Execution time	Memory
697506		hct_2so1	Discharging (NOI20_discharging)	C++14	100 / 100	119 ms	16064 KiB

Discharging

#include <bits/stdc++.h>

#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define all(v) (v).begin(), (v).end()
#define F first
#define S second
#define __builtin_popcount __builtin_popcountll
#define sz(v) ((int) (v).size())
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define pii(a, b) make_pair(a, b)

using namespace std;
typedef long long ll;

///

const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll oo = 1e18 + 7;

const int N = 1e6 + 5;

int n, a[N], nxt[N];
ll dp[N];

struct line
{
    ll a, b;
    line (const ll &_a, const ll &_b)
    {
        a = _a;
        b = _b;
    }
    ll eval(const ll &x)
    {
        return a * x + b;
    }
};

deque <line> st;

bool bad(const line &l1, const line &l2, const line &l3)
{
    return (long double) (l3.b - l1.b) * (l1.a - l2.a) < (long double) (l2.b - l1.b) * (l1.a - l3.a);
}

void add(const line &x)
{
    while (st.size() >= 2 && bad(st[st.size() - 2], st[st.size() - 1], x)) st.pop_back();
    st.push_back(x);
}

ll query(ll x)
{
    while (st.size() >= 2 && st[0].eval(x) >= st[1].eval(x)) st.pop_front();
    return st[0].eval(x);
}

void Input()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    nxt[1] = 1;
    for (int i = 2; i <= n; i ++)
        if (a[nxt[i - 1]] < a[i]) nxt[i] = i;
        else nxt[i] = nxt[i - 1];
}

void solve()
{
    add(line(0, 0));
    for (int i = 1; i <= n; i ++)
    {
        if (nxt[i] == i) dp[i] = query(a[i]) + 1LL * n * a[i];
        else dp[i] = dp[i - 1];
        add(line(-i, dp[i]));
    }
    cout << dp[n];
}

int main()
{
    std::ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("DIAMOND.inp", "r", stdin);
//    freopen("DIAMOND.out", "w", stdout);
    int test = 1;
    //cin >> test;
    while (test--)
    {
        Input();
        solve();
    }
    return 0;
}

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