Submission #285146

#	Time	Username	Problem	Language	Result	Execution time	Memory
285146		3zp	Discharging (NOI20_discharging)	C++14	100 / 100	144 ms	38264 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(1.0*(dp[i+1] - dp[j+1]) * (t[k] - t[i]) <= 1.0*(dp[i+1] - dp[k+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++;
        ad(i);
        while(Prev[j] >= i && cnt(j, u) >= cnt(Prev[j], u))
            j = Prev[j];
        dp[i] = cnt(j, u);
    }
    cout<<dp[1]<<endl;
}

Compilation message (stderr)

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

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