제출 #1265800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265800		nanaseyuzuki	Discharging (NOI20_discharging)	C++20	100 / 100	67 ms	16060 KiB

Discharging

#include <bits/stdc++.h>
/*
    --> Author: Kazuki_Hoshino__8703 <--
    I love Nanasaki Ai ☆*: .｡. o(≧▽≦)o .｡.:*☆
*/
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
using namespace std;

const int mn = 1e6 + 5;
const ll inf = 1e18;

int n, a[mn], prefix[mn], id[mn];
ll dp[mn];

struct line{double x, y; };

double center(line x, line y){
    return (x.y - y.y) / (y.x - x.x);
}

vector <line> reina;
vector <double> pts; 

void add(line kumiko){
    while(reina.size() && reina.back().x == kumiko.x && reina.back().y > kumiko.y){
        reina.pop_back();
        pts.pop_back();
    }
    while(reina.size() >= 2 && center(reina.back(), kumiko) <= pts.back()){
        reina.pop_back();
        pts.pop_back();
    }
    if(reina.size()) pts.push_back(center(reina.back(), kumiko));
    else pts.push_back(-inf);
    reina.push_back(kumiko);
}

ll query(int val){
    int id = upper_bound(pts.begin(), pts.end(), (double)val) - pts.begin() - 1;
    return (ll)reina[id].x * (ll)val + (ll)reina[id].y;
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        prefix[i] = max(prefix[i - 1], a[i]);
    
    }
    // dp[i] = dp[j] + prefix_max[i] * (n - j) = min(dp[j] - prefix_max[i] * j) + n * prefix_max[i]
    add({0, (double)prefix[0]});
    for(int i = 1; i <= n; i++){
        dp[i] = query(prefix[i]) + (ll)n * (ll)prefix[i];
        add({(double)-i, (double)dp[i]});
    }
    cout << dp[n];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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