Submission #697503

#	Time	Username	Problem	Language	Result	Execution time	Memory
697503		LeVanThuc	Discharging (NOI20_discharging)	C++17	100 / 100	175 ms	30260 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
    if(x>y)
    {
        x=y;
        return 1;
    }
    return 0;
}
void online()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
}
struct plane
{
    struct line
    {
        ll m,c;
        line(ll _m=0,ll _c=0)
        {
            this->m = _m;
            this->c = _c;
        }
        ll intersect(line &other)
        {
            return (this->c - other.c + other.m - this->m +1) / (other.m - this->m);
        }
        ll vl(ll x)
        {
            return this->m * x + this->c;
        }
    };

    deque<pair<line,ll>> dq;
    void insert(ll m,ll c)
    {
        line nex(m,c);
        if(this->dq.empty())
        {
            this->dq.push_back(pair<line,ll>(nex,0));
            return;
        }
        while(!this->dq.empty())
        {
            line pre=this->dq.back().fi;
            ll x=this->dq.back().se;
            if(nex.m==pre.m)
            {
                if(nex.c>pre.c) return;
            }
            else if(nex.intersect(pre)>x) break;
            this->dq.pop_back();

        }
        if(this->dq.empty())
        {
            this->dq.push_back(pair<line,ll>(nex,0));
            return;
        }
        dq.push_back(pair<line,ll>(nex,nex.intersect(dq.back().fi)));
    }

    ll query(ll x)
    {
        ll m = this->dq.size();
        while(m > 1 && dq[1].se <= x)
        {
            this->dq.pop_front();
            m--;
        }
        return this->dq.front().fi.vl(x);
    }

};
const ll N=1e6+10;
ll n,k;
ll ar[N],f[N],seg[N];
int main()
{
    online();
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>ar[i];
    }
    seg[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(ar[i]>ar[seg[i-1]]) seg[i]=i;
        else seg[i]=seg[i-1];
    }
    plane P;
    for(int i=1;i<=n;i++)
    {
        P.insert(n-i+1,f[i-1]);
        f[i]=P.query(ar[seg[i]]);
    }
    cout<<f[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