Submission #1201961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201961		pera	Building Bridges (CEOI17_building)	C++20	100 / 100	69 ms	15884 KiB

building

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1E6 , oo = 1E18;
struct line{
   int k = 0 , B = oo;
   int operator()(int x){
      return k * x + B;
   }
} t[N];
int lft[N] , rgt[N] , id = 0;
int new_node(){
   return ++id;
}
void insert(int root , int l , int r , line seg){
   if(l + 1 == r){
      if(seg(l) < t[root](l)){
         t[root] = seg;
      }
      return;
   }
   int mid = (l + r) >> 1;
   if(!lft[root]){
      lft[root] = new_node();
   }
   if(!rgt[root]){
      rgt[root] = new_node();
   }
   if(t[root].k < seg.k){
      swap(t[root] , seg);
   }
   if(t[root](mid) > seg(mid)){
      swap(t[root] , seg);
      insert(lft[root] , l , mid , seg);
   }else{
      insert(rgt[root] , mid , r , seg);
   }
}  
int query(int root , int l , int r , int pos){
   if(!root){
      return oo;
   }
   if(l + 1 == r){
      return t[root](l);
   }
   int mid = (l + r) >> 1;
   if(pos < mid){
      return min(t[root](pos) , query(lft[root] , l , mid , pos));
   }
   return min(t[root](pos) , query(rgt[root] , mid , r , pos));
}
signed main(){
   int n;
   cin >> n;
   new_node();
   vector<int> dp(n + 1) , H(n + 1) , W(n + 1) , sum(n + 1);
   for(int i = 1;i <= n;i ++){
      cin >> H[i];
   }
   for(int i = 1;i <= n;i ++){
      cin >> W[i];
      sum[i] += sum[i - 1] + W[i];
   }
   for(int i = 1;i <= n;i ++){
      int h , w;
      h = H[i];
      w = W[i];
      if(i > 1){
         dp[i] = query(1 , -N , N , h) + h * h + sum[i - 1];
      }else{
         dp[i] = 0;
      }
      insert(1 , -N , N , line(-2 * h , dp[i] + h * h - sum[i]));
   }
   cout << dp.back();
}

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