oj.uz

답안 #401348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401348 2021-05-09T22:55:22 Z gmyu Building Bridges (CEOI17_building) C++14
100 / 100
 62 ms 10452 KB 
/*
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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 4444 KB Output is correct
2 Correct 49 ms 4472 KB Output is correct
3 Correct 48 ms 4544 KB Output is correct
4 Correct 46 ms 4412 KB Output is correct
5 Correct 42 ms 5512 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 48 ms 4444 KB Output is correct
7 Correct 49 ms 4472 KB Output is correct
8 Correct 48 ms 4544 KB Output is correct
9 Correct 46 ms 4412 KB Output is correct
10 Correct 42 ms 5512 KB Output is correct
11 Correct 46 ms 4680 KB Output is correct
12 Correct 49 ms 4416 KB Output is correct
13 Correct 36 ms 4532 KB Output is correct
14 Correct 54 ms 4656 KB Output is correct
15 Correct 62 ms 10452 KB Output is correct
16 Correct 40 ms 5540 KB Output is correct
17 Correct 26 ms 4420 KB Output is correct
18 Correct 26 ms 4420 KB Output is correct