Submission #1178039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178039		vnedu	Discharging (NOI20_discharging)	C++20	100 / 100	101 ms	35832 KiB

Discharging

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

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "DISCHARGING"

/// end of template ///

const int N = 1e6 + 16;
int n,a[N];
namespace sub14
{
    bool check()
    {
        return (n<=1500);
    }
    const int N = 1515;
    ll dp[N];
    void solve()
    {
        dp[0]=0;
        for (int i=1; i<=n; ++i)
        {
            dp[i]=LLONG_MAX;
            int mx=0;
            for (int j=i; j>=1; --j)
            {
                maximize(mx,a[j]);
                minimize(dp[i],dp[j-1]+mx*1LL*(n-j+1));
            }
        }
//        for (int i=1; i<=n; ++i) cout<<dp[i]<<' ';
//        cout<<'\n';
        cout<<dp[n];
    }
}
namespace subfull
{
    struct line
    {
        ll a,b;
        int id;
        line() {}
        line(ll a, ll b, int id) : a(a),b(b),id(id) {}
        bool operator < (const line &S) const
        {
            return a>S.a;
        }
        double intersect(const line &S)
        {
            return (b-S.b)*1.0/(S.a-a);
        }
        ll getVal(ll x)
        {
            return a*x+b;
        }
    } m[N];
    stack<pair<line,int>> history;
    int numLine=0;
    void addLine(line cm)
    {
        while (numLine>1 && m[numLine-1].intersect(cm)<=m[numLine-1].intersect(m[numLine]))
        {
            history.push(make_pair(m[numLine],cm.id));
            --numLine;
        }
        m[++numLine]=cm;
    }
    void rollback()
    {
        line cm=m[numLine];
        --numLine;
        while (!history.empty() && history.top().se==cm.id)
        {
            m[++numLine]=history.top().fi;
            history.pop();
        }
    }
    ll cnpCHT(ll x)
    {
        int lo=1,hi=numLine-1,mid,cm=0;
        while (lo<=hi)
        {
            mid=(lo+hi)>>1;
            if (m[mid].intersect(m[mid+1])<=x*1.0) cm=mid,lo=mid+1;
            else hi=mid-1;
        }
        return m[cm+1].getVal(x);
    }
    stack<int> stk;
    ll dp[N];
    void solve()
    {
        for (int i=n; i>=1; --i)
        {
            while (!stk.empty() && a[stk.top()]<=a[i])
            {
                stk.pop();
                rollback();
            }
            addLine(line(a[i],dp[stk.empty()?n+1:stk.top()],i));
            dp[i]=cnpCHT(n-i+1);
            stk.push(i);
        }
//        for (int i=1; i<=n; ++i) cout<<dp[i]<<' ';
//        cout<<'\n';
        cout<<dp[1];
    }
}
void solve()
{
    cin>>n;
    for (int i=1; i<=n; ++i) cin>>a[i];
//    if (sub14::check()) return void(sub14::solve());
    return void(subfull::solve());
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

//    #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
//    cerr << "Time elapsed: " << TIME << " s.\n";
    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