Submission #232023

#	Time	Username	Problem	Language	Result	Execution time	Memory
232023		kimbj0709	Building Bridges (CEOI17_building)	C++14	100 / 100	125 ms	34924 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 400050
vector<int> vect3;
struct Line {
  int m, b;
  int operator()(int x) { return m * x + b; }
} a[maxn*4];
void insert(int l, int r, Line seg, int o) {
  if(l + 1 == r) {
    if(seg(vect3[l]) > a[o](vect3[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](vect3[mid]) < seg(vect3[mid])) {
    swap(a[o], seg);
    insert(l, mid, seg, lson);
  }
  else insert(mid, r, seg, rson);
}
int query(int l, int r, int x, int o) {
  if(l + 1 == r) return a[o](vect3[x]);
  int mid = (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;
  if(x < mid) return max(a[o](vect3[x]), query(l, mid, x, lson));
  else return max(a[o](vect3[x]), query(mid, r, x, rson));
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  for(int i=0;i<maxn*4;i++){
    a[i] = {(int)0,(int)(-10000000000000000)};
  }
  int no_of_input;
  cin >> no_of_input;
  int input;
  int s = 0;
  vector<int> vect1;
  set<int> set1;
  vector<int> vect2;
  vector<int> dp(no_of_input+1,0);
  for(int i=0;i<no_of_input;i++){
    cin >> input;
    set1.insert(input);
    vect1.push_back(input);
  }
  auto kk = set1.begin();
  while(kk!=set1.end()){
    vect3.push_back(*kk);
    kk++;
  }
  for(int i=0;i<no_of_input;i++){
    cin >> input;
    s += input;
    vect2.push_back(input);
  }
  dp[0] = 0;
  Line temp;
  temp.m = 2*vect1[0];
  temp.b = -(vect1[0]*vect1[0]-vect2[0]);
  insert(0,vect3.size()-1,temp,0);
  for(int i=1;i<no_of_input;i++){
    //cout << query(0,maxn,vect1[i],0) << endl;
    int lpos = lower_bound(vect3.begin(),vect3.end(),vect1[i])-vect3.begin();
    dp[i] = -query(0,vect3.size()-1,lpos,0)-vect2[i]+vect1[i]*vect1[i];
    Line temp;
    temp.m = 2*vect1[i];
    temp.b = -(vect1[i]*vect1[i]+dp[i]);
    //cout << temp.m << " " << temp.b << endl;
    insert(0,vect3.size()-1,temp,0);
  }
  /*for(int i=0;i<no_of_input;i++){
    cout << dp[i] << ' ';
  }
  cout << endl;*/
  cout << dp[no_of_input-1]+s;
}

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