제출 #285134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285134		3zp	Discharging (NOI20_discharging)	C++14	11 / 100	151 ms	31704 KiB

Discharging

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t[1000009],dp[1000009],Next[1000009],Prev[1000009];
stack<ll> S;
void rem(ll i){
    Next[Prev[i]] = Next[i];
    Prev[Next[i]] = Prev[i];
}
void ad(ll i){
    if(S.size() && t[S.top()] == t[i]) {rem(i); return;}
    while(S.size() >= 2){
        ll j = S.top(); S.pop();
        ll k = S.top();
        if((dp[j+1] - dp[i+1]) * (t[k] - t[i]) >= (dp[k+1] - dp[i+1]) * (t[j] - t[i])){
            rem(j);
            continue;
        }
        S.push(j);
        break;
    }
    S.push(i);
}
ll cnt(ll i, ll x){
    return  x * t[i]+ dp[i+1];

}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin>>n;
    for(ll i = 1;i <= n;i++){
        cin >> t[i];
        t[i] = max(t[i], t[i-1]);
        Next[i] = i+1;
        Prev[i] = i-1;
    }
    dp[n] = t[n];
    ad(n);
    ll j = n;
    ll u = 1;
    for(ll i = n-1; i >= 1; i--){
        u++;
        while(Prev[j] > 1 && cnt(j, u) >= cnt(Prev[j], u))
            j = Prev[j];
        dp[i] = cnt(j, u);
        ad(i);
    }
    cout<<dp[1]<<endl;
}

/*
dp[i] = dp[j+1] + (n-i+1)*a[j]

*/

컴파일 시 표준 에러 (stderr) 메시지

Discharging.cpp:28:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main(){
      |      ^

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