Submission #478249

#	Time	Username	Problem	Language	Result	Execution time	Memory
478249		KLPP	Building Bridges (CEOI17_building)	C++14	100 / 100	197 ms	12848 KiB

building

#include<bits/stdc++.h>

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long lld;
typedef long long ll;

bool query_flag = false;
struct line {
  long long m, c;
  mutable function<const line*()> succ;
  bool operator<(const line& o) const {
    if (!query_flag) return m < o.m;
    const line* s = succ();
    if (!s) return false;
    return (c - s->c) < (s->m - m) * o.m;
  }
};

struct maximum_hull : multiset<line> {
  bool bad(iterator y) {
    auto x = (y == begin()) ? end() : prev(y), z = next(y);
    if (x == end() && z == end()) return false;
    else if (x == end()) return y->m == z->m && y->c <= z->c;
    else if (z == end()) return y->m == x->m && y->c <= x->c;
    else return (x->c - y->c) * (z->m - y->m) >= (y->c - z->c) * (y->m - x->m);
  }
  void insert_line(const long long& m, const long long& c) {
    auto y = insert({ m, c, nullptr });
    y->succ = [=] { return next(y) == end() ? nullptr : &*next(y); };
    if (bad(y)) { erase(y); return; }
    iterator z;
    while ((z = next(y)) != end() && bad(z)) erase(z);
    while (y != begin() && bad(z = prev(y))) erase(z);
  }
  long long eval(long long x) {
    if (empty()) return numeric_limits<ll>::min();
    query_flag = true;
    auto l = *lower_bound({ x, 0, nullptr });
    query_flag = false;
    return l.m * x + l.c;
  }
};
maximum_hull M;
lld DP[1000000];
lld a[1000000];
lld b[1000000];

int main(){
	int n;
	cin>>n;
	rep(i,0,n)cin>>a[i];
	lld sum=0;
	rep(i,0,n)cin>>b[i],sum+=b[i];
	DP[0]=-b[0];
	M.insert_line(2*a[0],-(DP[0]+a[0]*a[0]));
	rep(i,1,n){
		DP[i]=-M.eval(a[i])+a[i]*a[i]-b[i];
		M.insert_line(2*a[i],-(DP[i]+a[i]*a[i]));
	}
	cout<<DP[n-1]+sum<<endl;
	
}

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