Submission #1181812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181812		Thunnus	Discharging (NOI20_discharging)	C++20	11 / 100	78 ms	40188 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)(c - other.c) / (other.m - m + EPS);
    }
};

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);
    queue<Line> buffer;
    dp[0] = n * a[0];
    dq.emplace_front(n, 0);
    for(int i = 1; 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]);
        Line line = {n - i, (i ? dp[i - 1] : 0)};
        buffer.emplace(line);
        if(!i || (a[i] > pref[i - 1])){
            while(!buffer.empty()){
                line = buffer.front();
                buffer.pop();
                while(sz(dq) >= 2 && line.x_int(dq.front()) <= dq.front().x_int(dq[1])){
                    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: 0 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 11 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28