Submission #231645

#	Time	Username	Problem	Language	Result	Execution time	Memory
231645		kimbj0709	Building Bridges (CEOI17_building)	C++14	30 / 100	46 ms	9336 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long long
#define maxn 100050
struct Line {
    ld m, b;
    ld operator()(ld x) { return m * x + b; }
  } a[maxn * 4];

  void insert(int l, int r, Line seg, int o) {
    if(l + 1 == r) {
      if(seg(l) > a[o](l)) a[o] = seg;
      return;
    }
    int mid= (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
    if(a[o].m > seg.m) swap(a[o], seg);
    if(a[o](mid) < seg(mid)) {
      swap(a[o], seg);
      insert(l, mid, seg, lson);
    }
    else insert(mid, r, seg, rson);
  }
  ld query(int l, int r, int x, int o) {
    if(l + 1 == r) return a[o](x);
    int mid = (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
    if(x < mid) return max(a[o](x), query(l, mid, x, lson));
    else return max(a[o](x), query(mid, r, x, rson));
  }
int32_t main(){
  ios::sync_with_stdio(0);
  int n;
  for(int i=0;i<4*maxn;i++){
      a[i] = {-0,-LLONG_MAX};
  }
  cin >> n;
  int input;
  vector<int> vect1,vect2;
  for(int i=0;i<n;i++){
    cin >> input;
    vect1.push_back(input);
  }
  for(int i=0;i<n;i++){
    cin >> input;
    vect2.push_back(input);
  }
  vect2[0] = 0;
  for(int i=1;i<n;i++){
    vect2[i] += vect2[i-1];
  }
  vector<int> dp(n,0);
  insert(0,n,{2*vect1[0],-vect1[0]*vect1[0]},0);
  for(int i=1;i<n;i++){
    dp[i] = -query(0,n,vect1[i],0)+vect2[i-1]+vect1[i]*vect1[i];
    insert(0,n,{2*vect1[i],-dp[i]+vect2[i]-vect1[i]*vect1[i]},0);
  }
  cout << dp[n-1];
}

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