제출 #1182199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182199		Thunnus	Discharging (NOI20_discharging)	C++20	11 / 100	75 ms	23880 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);
    dp[0] = n * a[0];
    dq.emplace_front(n, 0);
    Line line;
    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 = {n - i, (i ? dp[i - 1] : 0)};
        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