Submission #967355

#	Time	Username	Problem	Language	Result	Execution time	Memory
967355		tminh_hk20	Building Bridges (CEOI17_building)	C++14	100 / 100	74 ms	13136 KiB

building

/*
    Task:
    Point:
    Tag:
*/

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define int long long
#define ii pair<int,int>
#define getbit(x,y) (x>>y &1)
#define turnon(x,y) (x | (1<<y))
#define turnoff(x,y) (x ^ (1<<y))

using namespace std;
const int N = 2e5;
const int MOD = 1e9+7;
const int MOD2 =  1e9+2277;
const int MOD3 = 1e9+9;
const int base = 311;
const int BSIZE = 320;

int T=1;

struct Line {
    bool t;
	double x;
	int a, b;
};
bool operator<(Line l1, Line l2) {
	if (l1.t || l2.t) return l1.x < l2.x;
	return l1.a > l2.a;
}

struct Dynamic_ConvexHull{
    set<Line> l;
    // each A has a smallest B so we use set
    bool left(set<Line>::iterator it){
        return it != l.begin();
    }

    bool right(set<Line>::iterator it){
        return it != l.end() && (++it) != l.end();
    }

    double insec(Line x, Line y){
        return 1.0*(y.b-x.b)/(x.a-y.a);
    }

    int eval(int x, Line y){
        return x*y.a+y.b;
    }

    auto lit(set<Line>::iterator it){ return --it;};
    auto rit(set<Line>::iterator it){ return ++it;};
    void calcx(set<Line>::iterator it){
        if (left(it)){
            Line l1 = *it;
            Line l2 = *lit(it);
            l1.x = insec(l2,l1);
            l.erase(it); l.insert(l1);
        }
    }

    bool bad(set<Line>::iterator it){
        return (left(it) && right(it) && insec(*lit(it),*rit(it))<=insec(*lit(it),*it));
    }

    void add(int a, int b){
        set<Line>::iterator it;

        //find A exist in set then take smallest B
        it = l.lower_bound({0,0,a,b});
        if (it != l.end() && (*it).a == a){
            if ((*it).b<=b) return;
            l.erase(it);
        }

        it = l.insert({0,0,a,b}).first;
        if (bad(it)) l.erase(it);
        else{
            while(right(it) && bad(rit(it))) l.erase(rit(it));
            while(left(it) && bad(lit(it))) l.erase(lit(it));

            if (right(it)) calcx(rit(it));
            calcx(it);
        }
    }

    int get(int x){
        Line y = *(--l.upper_bound({1,1.0*x,0,0}));
        return eval(x,y);
    }



};

int n, h[N+10], w[N+10], dp[N+10], tot = 0;
Dynamic_ConvexHull cht;

void solve(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> h[i];
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		tot += w[i];
	}

	dp[1] = -w[1];
	for (int i = 2; i <= n; i++) {
		cht.add(-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1]);
		dp[i] = cht.get(h[i]) - w[i] + h[i] * h[i];
	}


    cout << tot+dp[n];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

//    cin>> T;
    while(T--) solve();

}

//TRUONG TAN MINH HK20

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