Submission #401348

#	Time	Username	Problem	Language	Result	Execution time	Memory
401348		gmyu	Building Bridges (CEOI17_building)	C++14	100 / 100	62 ms	10452 KiB

building

/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/CEOI17_building
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()
#define adjread {int a, b; cin >> a >> b; adjlist[a].pb(b); adjlist[b].pb(a); }

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007


bool debug;

int N;
ll h[MAXV], w[MAXV], psw[MAXV];
ll dp[MAXV];

/**
 * Author: Simon Lindholm
 * Date: 2017-04-20
 * License: CC0
 * Source: own work
 * Description: Container where you can add lines of the form kx+m, and query maximum values at points x.
 *  lower convext hull
 *  Useful for dynamic programming (``convex hull trick'').
 * Time: O(\log N)
 * Status: stress-tested
 * https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LineContainer.h
 * usage example: https://oj.uz/submission/237141
 */
#include <assert.h>     /* assert */

int lc_comp_type = 1;
struct Line {
    /// y = kx + m; p is the intersection point of line y and the next line on the convex hull
	mutable ll k, m, p;     // can add additional info such as id
	bool operator<(const Line& o) const {
	    if(lc_comp_type == 1) {
            return k < o.k;
	    } else {
	        return p < o.p;
	    }
    }
	//bool operator<(const ll& x) const { return p < x; }
};

struct LineContainer {
    multiset<Line> hull;
    int hull_type = 1;  /// 1 for max val (lower convex hull), -1 for min val (upper convex hull)
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll lc_inf = 1LL << 62;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(multiset<Line>::iterator x, multiset<Line>::iterator y) {
		if (y == hull.end()) { x->p = lc_inf; return false; }
		if (x->k == y->k) x->p = (x->m > y->m) ? lc_inf : -lc_inf;
		else x->p = div(y->m - x->m, x->k - y->k);      // p is the intersect against next line
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
	    /// if, instead of max val (lower convex hull), we need min val (upper convex hull), we flip the hull
	    k *= (ll)hull_type; m *= (ll)hull_type;
		auto z = hull.insert({k, m, 0}), y = z, x = y;
		z++;
		while (isect(y, z)) z = hull.erase(z);
		if (x != hull.begin() && isect(--x, y)) isect(x, y = hull.erase(y));
		while ((y = x) != hull.begin() && (--x)->p >= y->p)
			isect(x, hull.erase(y));
	}
	ll query(ll x) {
		assert(!hull.empty());
		Line ql; ql.p = x;
		lc_comp_type = 2;
		auto l = *hull.lower_bound(ql);
		lc_comp_type = 1;
		return (l.k * x + l.m) * (ll)hull_type;
	}
};

Line l;
LineContainer lc;

int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N ;
    for(int i=1;i<=N;i++) {
        cin >> h[i];
    }
    for(int i=1;i<=N;i++) {
        cin >> w[i];
        psw[i] = psw[i-1] + w[i];
    }

    lc.hull_type = -1;
    dp[1] = 0;
    lc.add(-2LL*h[1], dp[1]-psw[1]+h[1]*h[1]);

    for(int i=2;i<=N;i++) {
        dp[i] = lc.query(h[i]) + h[i] * h[i] + psw[i-1];
        if(debug) cout << dp[i] << endl;
        lc.add(-2LL*h[i], dp[i]-psw[i]+h[i]*h[i]);
    }
    cout << dp[N] << endl;


    if(debug) cout << endl << "EOL" << endl;
}

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