oj.uz

Submission #527025

# Submission time Handle Problem Language Result Execution time Memory
527025 2022-02-16T19:57:15 Z inluminas Building Bridges (CEOI17_building) C++17
100 / 100
 63 ms 8496 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 ll lmt=1e5+2;
ll 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,ll L=1,ll R=n,ll at=1){
  ll 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,ll L=1,ll R=n,ll at=1){
  ll 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(ll i=1;i<=n;i++){
    cin>>h[i];
    h2[i]=h[i];
  }
  sort(h2+1,h2+n+1);
  ll sum=0;
  for(ll i=1;i<=n;i++){
    cin>>w[i];
    sum+=w[i];
  }
  ll dp=sum-w[1];
  for(ll 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 2 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 7316 KB Output is correct
2 Correct 55 ms 8340 KB Output is correct
3 Correct 55 ms 8372 KB Output is correct
4 Correct 63 ms 8168 KB Output is correct
5 Correct 33 ms 8236 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 57 ms 7316 KB Output is correct
7 Correct 55 ms 8340 KB Output is correct
8 Correct 55 ms 8372 KB Output is correct
9 Correct 63 ms 8168 KB Output is correct
10 Correct 33 ms 8236 KB Output is correct
11 Correct 61 ms 8492 KB Output is correct
12 Correct 54 ms 8352 KB Output is correct
13 Correct 46 ms 8424 KB Output is correct
14 Correct 55 ms 8496 KB Output is correct
15 Correct 33 ms 8132 KB Output is correct
16 Correct 33 ms 8248 KB Output is correct
17 Correct 32 ms 8336 KB Output is correct
18 Correct 28 ms 8392 KB Output is correct