Submission #241114

#TimeUsernameProblemLanguageResultExecution timeMemory
241114kimbj0709Building Bridges (CEOI17_building)C++14
100 / 100
116 ms16108 KiB
    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define maxn 100050
    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==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+1, r, seg, rson);
    }
    int query(int l, int r, int x, int o) {
      if(l==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+1, 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;
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...