Submission #349409

#	Time	Username	Problem	Language	Result	Execution time	Memory
349409		doowey	Building Bridges (CEOI17_building)	C++14	100 / 100	90 ms	12524 KiB

building

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
const ll inf = (ll)1e18;
const ld INF = (ld)4e18;
int h[N];
ll w[N];
ll dp[N];

ll sq(ll x){
    return (x * 1ll * x);
}

bool Q;

struct Line{
  ll ai;
  ll bi;
  mutable ld ri;
  bool operator< (const Line &T) const {
    if(Q) return ai < T.ai;
    else return ri < T.ri;
  }
};

struct Hull : multiset<Line>{
  ld div(ld a, ld b){
    return a/b;
  }
  ld inter(Line A, Line B){
    return div((A.bi)-(B.bi),(B.ai)-(A.ai));
  }
  bool hasl(iterator it){
    return (it != begin());
  }
  bool har(iterator it){
    it++;
    return (it != end());
  }
  bool bad(iterator it){
    if(!hasl(it) || !har(it)) return false;
    auto pv = it;
    auto nx = it;
    pv -- ;
    nx ++ ;
    return inter(*pv,*nx) <= inter(*pv,*it);
  }
  void upd(iterator &it){
    auto ni = it;
    ni ++ ;
    if(ni == end()){
      it->ri = INF;
    }
    else{
      it->ri = inter(*it, *ni);
    }
  }
  void add(ll ai, ll bi){
    ai=-ai;
    bi=-bi;
    Q = true;
    Line cur = {ai, bi, inf};
    auto it = lower_bound(cur);
    if(it != end()){
      if(it->ai == ai){
        if(it->bi >= bi){
          return;
        }
        else{
          it=erase(it); //
        }
      }
    }
    it=insert(cur);
    if(bad(it)){
      erase(it);
      return;
    }
    auto nx = it;
    nx++;
    while(1){
      if(nx==end()) break;
      if(bad(nx))nx=erase(nx);
      else break;
    }
    nx = it;
    while(1){
      if(it==begin()) break;
      nx=it;
      nx--;
      if(bad(nx))erase(nx);
      else break;
    }
    upd(it);
    nx = it;
    if(nx != begin()){
      nx--;
      upd(nx);
    }
  }
  ll query(ld xi){
    Q = false;
    auto it = lower_bound({0,0,xi});
    return -((it->ai) * xi + (it->bi));
  }
};

ll ax[N];
ll bx[N];

int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> h[i];
    }
    for(int i = 1; i <= n; i ++ ){
        cin >> w[i];
        w[i] += w[i - 1];
        dp[i]=inf;
    }
    dp[1]=0;
    Hull dpv;
    for(int i = 1; i <= n; i ++ ){
        if(i > 1){
            dp[i]=dpv.query(h[i])+sq(h[i])+w[i-1];
        }
        ax[i]=-2ll*h[i];
        bx[i]=sq(h[i])-w[i]+dp[i];
        dpv.add(ax[i],bx[i]);
    }
    cout << dp[n];
    return 0;
}

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