Submission #267135

#	Time	Username	Problem	Language	Result	Execution time	Memory
267135		eohomegrownapps	Discharging (NOI20_discharging)	C++14	100 / 100	891 ms	6904 KiB

Discharging

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

typedef long long ll;
typedef long double ld;

struct Line{
    ll m, c;
    Line(ll _m, ll _c){
        m=_m;c=_c;
    }

    ll f(ll x){
        return m*x+c;
    }

    ld intersectX(Line l){
        return (1.0*l.c-c)/(m-l.m);
    }
};

deque<Line> hull;

bool isBetter(Line l){
    return (l.intersectX(hull[hull.size()-1])<l.intersectX(hull[hull.size()-2]));
}

void add(Line l){
    if (hull.size()>0&&hull.back().m==l.m){
        if (l.c<hull.back().c){
            hull.pop_back();
            hull.push_back(l);
        }
        return;
    }
    while (hull.size()>1&&isBetter(l)){
        hull.pop_back();
    }
    hull.push_back(l);
}

ll query(ll x){
    while (hull.size()>1&&hull[0].f(x)>hull[1].f(x)){
        hull.pop_front();
    }
    return hull.front().f(x);
}

int main(){
    ll n;
    cin>>n;
    add(Line(n,0));
    ll prev = 0;
    ll ans;
    for (ll i = 1; i<=n; i++){
        ll val;
        cin>>val;
        if (val<prev){
            val=prev;
        }
        /*cout<<"val: "<<val<<'\n';
        for (auto h : hull){
            cout<<h.m<<' '<<h.c<<'\n';
        }*/
        prev=val;
        ans = query(val);
        add(Line{n-i,ans});
        //cout<<ans<<'\n';
    }
    cout<<ans<<'\n';
}

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