oj.uz

Submission #285134

# Submission time Handle Problem Language Result Execution time Memory
285134 2020-08-28T10:56:28 Z 3zp Discharging (NOI20_discharging) C++14
11 / 100
 151 ms 31704 KB 
#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]

*/

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 31608 KB Output is correct
2 Correct 139 ms 31644 KB Output is correct
3 Correct 151 ms 31608 KB Output is correct
4 Correct 140 ms 31608 KB Output is correct
5 Correct 134 ms 31592 KB Output is correct
6 Correct 133 ms 31676 KB Output is correct
7 Correct 141 ms 31704 KB Output is correct
8 Correct 140 ms 31608 KB Output is correct
9 Correct 136 ms 31608 KB Output is correct
10 Correct 136 ms 31664 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -