Submission #1182207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182207		Thunnus	Discharging (NOI20_discharging)	C++20	100 / 100	135 ms	25880 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const long double EPS = 1e-12;

struct Line{
    int m, c;
    Line(int m, int c) : m(m), c(c) {}
    Line() : Line(0, 0) {}

    inline int eval(int x){
        return m * x + c;
    }

    inline long double x_int(Line &other){
        return (long double)(other.c - c) / (m - other.m + EPS);
    }
};

inline bool bad(Line &a, Line &b, Line &c){
    return a.x_int(c) <= a.x_int(b);
}

inline void solve(){
    int n;
    cin >> n;
    vi a(n), pref(n);
    for(int &i : a){
        cin >> i;
    }
    pref.front() = a.front();
    for(int i = 1; i < n; i++){
        pref[i] = max(pref[i - 1], a[i]);
    }
    // in an optimal grouping, pref[i] must belongs to the last group. 
	// dp[i] = contribution of grouping from 1 to i to the final grouping
    deque<Line> dq;
    vi dp(n);
    dq.emplace_front(0, 0);
    Line line;
    for(int i = 0; i < n; i++){
        while(sz(dq) >= 2 && dq.back().eval(pref[i]) >= dq[sz(dq) - 2].eval(pref[i])){
            dq.pop_back();
        }
        dp[i] = dq.back().eval(pref[i]) + pref[i] * n;
        line = {-i - 1, dp[i]};
        while(sz(dq) >= 2 && bad(dq[1], dq[0], line)){
            dq.pop_front();
        }
        dq.emplace_front(line);
    }
    cout << dp[n - 1] << "\n";
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    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