oj.uz

Submission #524048

# Submission time Handle Problem Language Result Execution time Memory
524048 2022-02-08T14:46:20 Z DanerZein Discharging (NOI20_discharging) C++14
38 / 100
 747 ms 17704 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e6+10;
struct line{
  ll m,b;
  line(ll mm,ll bb){
    m=mm; b=bb;
  }
  ll eval(ll x){
    return m*x+b;
  }
  /*long double intersect(line l){
    return (long double)(b-l.b)/(l.m-m);
  }*/
   ll intersect(line l){
    ll le=1;
    ll ri=1;
    while(eval(ri)>l.eval(ri)){
      le=ri;
      ri*=2;
    }
    while(ri>le){
      ll mid=(le+ri)/2;
      if(eval(mid)<=l.eval(mid)) ri=mid;
      else le=mid+1;
    }
    return ri;
  }
};
ll val[MAX_N];
int main(){
  int n; cin>>n;
  for(int i=1;i<=n;i++){
    cin>>val[i];
  }
  deque<line> dq;
  dq.push_front({0,0});
  ll ans=0;
  for(int i=1;i<=n;i++){
    int t=dq.size();
    line nl={-i,ans};
    while(t>=2 && nl.intersect(dq[t-2])<=dq[t-1].intersect(dq[t-2])){
      dq.pop_back();
      t--;
    }
    dq.push_back(nl);
    while(dq.size()>=2 && dq[0].eval(val[i])>=dq[1].eval(val[i]))
      dq.pop_front();
    ans=dq.front().eval(val[i])+val[i]*(n+1);
  }
  cout<<ans<<endl;
}

Subtask #1
0 / 9.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 304 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 316 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 312 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 280 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 2 ms 204 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 304 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 2 ms 316 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 2 ms 312 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 280 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 2 ms 204 KB Output is correct
16 Correct 537 ms 12940 KB Output is correct
17 Correct 624 ms 12952 KB Output is correct
18 Correct 453 ms 12512 KB Output is correct
19 Correct 627 ms 12832 KB Output is correct
20 Correct 631 ms 12964 KB Output is correct
21 Correct 615 ms 12940 KB Output is correct
22 Correct 563 ms 13476 KB Output is correct
23 Correct 701 ms 14516 KB Output is correct
24 Correct 634 ms 14096 KB Output is correct
25 Correct 695 ms 14388 KB Output is correct
26 Correct 747 ms 14532 KB Output is correct
27 Correct 528 ms 13124 KB Output is correct
28 Correct 656 ms 14200 KB Output is correct
29 Correct 691 ms 14276 KB Output is correct
30 Correct 741 ms 14472 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 28.0

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