oj.uz

Submission #967357

# Submission time Handle Problem Language Result Execution time Memory
967357 2024-04-22T03:02:01 Z tminh_hk20 Building Bridges (CEOI17_building) C++14
100 / 100
 71 ms 12400 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(auto it){
        return it != l.begin();
    }

    bool right(auto 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(auto it){ return --it;};
    auto rit(auto it){ return ++it;};
    void calcx(auto it){
        if (left(it)){
            Line l1 = *it;
            Line l2 = *lit(it);
            l1.x = insec(l2,l1);
            l.erase(it); l.insert(l1);
        }
    }

    bool bad(auto it){
        return (left(it) && right(it) && insec(*lit(it),*rit(it))<=insec(*lit(it),*it));
    }

    void add(int a, int b){

        //find A exist in set then take smallest B
        auto 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

Compilation message

building.cpp:40:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   40 |     bool left(auto it){
      |               ^~~~
building.cpp:44:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   44 |     bool right(auto it){
      |                ^~~~
building.cpp:56:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   56 |     auto lit(auto it){ return --it;};
      |              ^~~~
building.cpp:57:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   57 |     auto rit(auto it){ return ++it;};
      |              ^~~~
building.cpp:58:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   58 |     void calcx(auto it){
      |                ^~~~
building.cpp:67:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   67 |     bool bad(auto it){
      |              ^~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4700 KB Output is correct
2 Correct 58 ms 4792 KB Output is correct
3 Correct 57 ms 4816 KB Output is correct
4 Correct 54 ms 4696 KB Output is correct
5 Correct 54 ms 6236 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 58 ms 4700 KB Output is correct
7 Correct 58 ms 4792 KB Output is correct
8 Correct 57 ms 4816 KB Output is correct
9 Correct 54 ms 4696 KB Output is correct
10 Correct 54 ms 6236 KB Output is correct
11 Correct 52 ms 4696 KB Output is correct
12 Correct 60 ms 4784 KB Output is correct
13 Correct 38 ms 4588 KB Output is correct
14 Correct 56 ms 4688 KB Output is correct
15 Correct 71 ms 12400 KB Output is correct
16 Correct 55 ms 6224 KB Output is correct
17 Correct 12 ms 4696 KB Output is correct
18 Correct 16 ms 4700 KB Output is correct