oj.uz

Submission #967355

# Submission time Handle Problem Language Result Execution time Memory
967355 2024-04-22T03:00:25 Z tminh_hk20 Building Bridges (CEOI17_building) C++14
100 / 100
 74 ms 13136 KB 
/*
    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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4568 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 5456 KB Output is correct
2 Correct 58 ms 5556 KB Output is correct
3 Correct 59 ms 5588 KB Output is correct
4 Correct 55 ms 5412 KB Output is correct
5 Correct 54 ms 7028 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4568 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 63 ms 5456 KB Output is correct
7 Correct 58 ms 5556 KB Output is correct
8 Correct 59 ms 5588 KB Output is correct
9 Correct 55 ms 5412 KB Output is correct
10 Correct 54 ms 7028 KB Output is correct
11 Correct 52 ms 5456 KB Output is correct
12 Correct 60 ms 5460 KB Output is correct
13 Correct 43 ms 5364 KB Output is correct
14 Correct 56 ms 5460 KB Output is correct
15 Correct 74 ms 13136 KB Output is correct
16 Correct 54 ms 6848 KB Output is correct
17 Correct 13 ms 5456 KB Output is correct
18 Correct 15 ms 5856 KB Output is correct