Submission #697485

#	Time	Username	Problem	Language	Result	Execution time	Memory
697485		Bobonbush	Discharging (NOI20_discharging)	C++17	47 / 100	324 ms	86660 KiB

Discharging

#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll ;
const int LOG = 18;
const long long base = 31;
const long long MODULO = 1e9+7;
const long long INF = 1e18+1;
template<class X ,class Y>
    bool Minimize(X &x , Y y)
    {
        if(x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X , class Y>
    bool Maximize(X &x , Y y)
    {
        if(x < y)
        {
            x = y;
            return true;
        }
        return false;
    }
const int N = 1e6+1;
int n , k ;
long long dp[N];
int a[N];

class SegmentedTree
{
    private:
        vector<pair<long long , long long >>nodes;
    public:
        SegmentedTree(int _n)
        {
            nodes.assign(_n * 4 + 1 , make_pair(INF , INF));
        }

        void Down(int id ,long long lazy)
        {
            Minimize(nodes[id].first , lazy);
            Minimize(nodes[id].second , lazy);
        }

        void Update(int l ,int r ,int id , int u ,int v ,long long w)
        {
            if(l > v  || u > r)
            {
                return ;
            }
            if(u <= l && r <= v)
            {
                Minimize(nodes[id].first , w);
                Minimize(nodes[id].second , w);
                return ;
            }
            int mid = (l+r) >> 1;
            Down(id << 1 , nodes[id].second);
            Down(id << 1 |1 , nodes[id].second);
            nodes[id].second = INF;
            Update(l , mid ,id << 1 , u ,v , w);
            Update(mid+1 , r , id <<1 |1 , u , v , w);

            nodes[id].first = min(nodes[id << 1].first , nodes[id << 1 | 1].first);
        }

        long long Get(int l,int r ,int id ,int u ,int v)
        {
            if(l > v || u > r)
            {
                return INF;
            }
            if(u <= l && r <= v)
            {
                return nodes[id].first;
            }
            int mid = (l+r) >> 1;
            Down(id << 1 , nodes[id].second);
            Down(id << 1 |1 , nodes[id].second);
            nodes[id].second = INF;
            return min(Get(l , mid , id << 1 , u , v) , Get(mid+1 , r , id << 1 |1 , u , v));
        }
};

int lll[N] ,rr[N];
void Input()
{
    cin >> n ;
    for(int i = 1; i <= n ; i++)
    {
        cin >> a[i];
    }
}
void Process()
{
    SegmentedTree Seg(n);
    stack<int>st;
    for(int i =1; i <= n ; i++)
    {
        while(!st.empty() && a[st.top()] <= a[i])
        {
            st.pop();
        }
        lll[i] = 1;
        if(!st.empty())lll[i] = st.top() + 1;
        st.push(i);
    }
    while(!st.empty())st.pop();
    for(int i = n ; i >= 1 ; i--)
    {
        while(!st.empty() && a[st.top()] <= a[i])st.pop();
        rr[i] = n;
        if(!st.empty())rr[i] = st.top() -1;
        st.push(i);
    }
    for(int i = 1 ; i <= n ; i++)dp[i] = INF;
    for(int i = 1; i <= n ; i++)
    {
        int maxx = a[i];
        for(int j = i ; j>=1 && (n * 1LL * (i - j +1)) <= 1e8 ; j--)
        {
            Maximize(maxx , a[j]);

            Minimize(dp[i] , dp[j-1]  + maxx * 1LL * (n - j + 1));

        }
        if(a[lll[i] -1] > a[i])
            Minimize(dp[i] , dp[lll[i] -1]);
    }
    cout << dp[n];
}
int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    int test = 1;
    while(test--)
    {
        Input();
        Process();
    }
    return 0;
}

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