oj.uz

Submission #527024

# Submission time Handle Problem Language Result Execution time Memory
527024 2022-02-16T19:56:35 Z inluminas Building Bridges (CEOI17_building) C++17
30 / 100
 44 ms 6192 KB 
#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const int lmt=1e5+2;
int h[lmt],n,h2[lmt],w[lmt];
vector<pair<ll,ll>>tree(3*lmt,{0,1e14});

ll f(pair<ll,ll>line,ll x){//line.first=m,line.second=c
  return line.first*x+line.second;
}

void update(pair<ll,ll>line,int L=1,int R=n,int at=1){
  int mid=(L+R)>>1;
  bool lft=f(line,h2[L])<f(tree[at],h2[L]);
  bool md=f(line,h2[mid])<f(tree[at],h2[mid]);

  if(md) swap(tree[at],line);

  if(L==R) return;
  else if(lft!=md) update(line,L,mid,at*2);
  else update(line,mid+1,R,at*2+1);
}

ll query(ll x,int L=1,int R=n,int at=1){
  int mid=(L+R)>>1;
  ll cur=f(tree[at],x);
  if(L==R) return cur;
  if(x<=h2[mid]) return min(cur,query(x,L,mid,at*2));
  else return min(cur,query(x,mid+1,R,at*2+1));
}

int main(){
  fastio;

  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>h[i];
    h2[i]=h[i];
  }
  sort(h2+1,h2+n+1);
  ll sum=0;
  for(int i=1;i<=n;i++){
    cin>>w[i];
    sum+=w[i];
  }
  ll dp=sum-w[1];
  for(int i=1;i<=n;i++){
    if(i>1) dp=query(h[i])+h[i]*h[i]-w[i];
    update({-2*h[i],dp+h[i]*h[i]});
  }
  cout<<dp<<endl;
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 5040 KB Output is correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 5040 KB Output is correct
6 Incorrect 44 ms 6192 KB Output isn't correct
7 Halted 0 ms 0 KB -