Submission #468690

#	Time	Username	Problem	Language	Result	Execution time	Memory
468690		ivan_tudor	Building Bridges (CEOI17_building)	C++14	0 / 100	39 ms	9100 KiB

building

#include<bits/stdc++.h>
using namespace std;
struct functie{
  long long a , b;
  long long operator () (int x) {
    return 1LL * a * x  + b;
  }
  functie(){
    a = 0;
    b = LLONG_MAX;
  }
  functie(long long _a ,long long _b){
    a = _a;
    b = _b;
  }
};
const int N = 1E5 + 5;
functie lichao[4 * N];
void ins(int nod, int l, int r, functie f){
  int mid = (l + r)/2;
  if(lichao[nod](mid) > f(mid))
    swap(lichao[nod], f);
  if(l == r)
    return;
  if(f(l) < lichao[nod](l))
    ins(2*nod, l, mid, f);
  if(f(r) < lichao[nod](r))
    ins(2*nod + 1, mid + 1, r, f);
}
long long querymin(int nod, int l, int r, int p){
  if(p < l || r < p)
    return LLONG_MAX;
  int mid = (l + r)/2;
  long long cans = lichao[nod](p);
  if(l == r)
    return cans;
  if(p <= mid)
    return min(cans, querymin(2*nod, l, mid, p));
  else
    return min(cans, querymin(2*nod + 1, mid + 1, r, p));
}
long long h[N], dp[N], s[N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i = 1; i<=n; i++)
    cin>>h[i];
  for(int i = 1; i<=n; i++){
    cin>>s[i];
    s[i] += s[i - 1];
  }
  dp[1] = 0;
  ins(1, 1, N, {-2 * h[1], 1LL * h[1] * h[1] + dp[1] - s[1]});
  for(int i = 2; i<=n; i++){
    dp[i] = h[i] * h[i] + s[i - 1] + querymin(1, 1, N, h[i]);
    ins(1, 1, N, {- 2 * h[i], h[i] * h[i] + dp[i] - s[i]});
  }
  cout<<dp[n];
  return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40