oj.uz

Submission #285144

# Submission time Handle Problem Language Result Execution time Memory
285144 2020-08-28T11:12:31 Z 3zp Discharging (NOI20_discharging) C++14
20 / 100
 140 ms 31736 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[i+1] - dp[j+1]) * (t[k] - t[i]) <= (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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct

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 140 ms 31736 KB Output is correct
2 Correct 134 ms 31736 KB Output is correct
3 Correct 134 ms 31608 KB Output is correct
4 Correct 133 ms 31688 KB Output is correct
5 Correct 134 ms 31652 KB Output is correct
6 Correct 134 ms 31644 KB Output is correct
7 Correct 132 ms 31608 KB Output is correct
8 Correct 131 ms 31668 KB Output is correct
9 Correct 134 ms 31608 KB Output is correct
10 Correct 131 ms 31668 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Incorrect 1 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Incorrect 1 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -