Submission #320646

#	Time	Username	Problem	Language	Result	Execution time	Memory
320646		egas	Discharging (NOI20_discharging)	C++14	100 / 100	185 ms	23968 KiB

Discharging

#include <bits/stdc++.h>

using namespace std;

class CHT {

private:

    class Line {

        long long m,c;

    public:

        Line(long long m,long long c) {

            this->m=m;

            this->c=c;

        }

        long long getVal(long long x) {

            return this->m*x + c;

        }

        long long intersect(Line &a) {

            return ceil((a.c - this->c)/(long double)(this->m - a.m));

        }

    };

    deque<pair<Line,long long>> dq;

public:

    void insert(long long m,long long c) {

        Line temp(m,c);

        while(dq.size()>1 and dq.back().second>=dq.back().first.intersect(temp)) {

            dq.pop_back();

        }

        if(dq.size()==0) {

            dq.push_back({temp,0});

        } else {

            dq.push_back({temp,dq.back().first.intersect(temp)});

        }

    }

    long long query(long long x) {

        while(dq.size()>1) {

            if(dq[1].second<=x) {

                dq.pop_front();

            } else {

                break;

            }

        }

        return dq[0].first.getVal(x);

    }

};

int32_t main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    long long n;

    cin >> n;

    vector<long long> a(n);

    for(long long i = 0 ; i < n ; i++) {

        cin >> a[i];

    }

    long long dp[n];

    dp[0]=a[0]*n;

    long long maxi[n];

    maxi[0]=a[0];

    for(long long i = 0 ; i < n ; i++) {

        if(i==0) {

            continue;

        }

        maxi[i]=max(maxi[i-1],a[i]);

    }

    CHT meat;

    meat.insert(n,0);

    for(long long i = 0 ; i < n ; i++) {

        if(i==0)continue;

        meat.insert(n-i,dp[i-1]);

        dp[i]=meat.query(maxi[i]);

    }

    cout << dp[n-1] << '\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