oj.uz

Submission #898343

# Submission time Handle Problem Language Result Execution time Memory
898343 2024-01-04T14:10:16 Z dwuy Building Bridges (CEOI17_building) C++14
100 / 100
 85 ms 14768 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int OO = 1e18;

struct Line{
    int m, b;
    mutable function<const Line *()> succ;

    Line(int m=0, int b=OO){
        this->m = m;
        this->b = b;
    }

    bool operator < (const Line &other) const{
        if(other.b != OO) return this->m < other.m;
        auto nxt = succ();
        if(!nxt) return 0;
        return b - nxt->b < other.m*(nxt->m - m);
    }
};

struct Line_container : public multiset<Line>{
    bool bad(iterator cur){
        auto nxt = next(cur);
        if(cur == begin()){
            if(nxt==end()) return 0;
            return cur->m == nxt->m && cur->b == nxt->b;
        }
        auto pre = prev(cur);
        if(nxt == end()) return cur->m == pre->m && cur->b == pre->b;
        return (pre->b - cur->b)*(nxt->m - cur->m) >= (cur->b - nxt->b)*(cur->m - pre->m);
    }

    void add(Line line){
        line.m *= -1;
        line.b *= -1;
        auto cur = insert(line);
        cur->succ = [=] {return next(cur)==end()? 0 : &*next(cur);};
        if(bad(cur)){
            erase(cur);
            return;
        }
        while(next(cur)!=end() && bad(next(cur))) erase(next(cur));
        while(cur!=begin() && bad(prev(cur))) erase(prev(cur));
    }

    int get(int val){
        auto itr = lower_bound(Line(val));
        if(itr == end()) return 0;
        return val*itr->m + itr->b;
    }
};

const int MX = 200005;
int n;
int h[MX];
int c[MX];
int dp[MX];

void nhap(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> h[i];
    for(int i=1; i<=n; i++) cin >> c[i], c[i] += c[i-1];
}


int sqr(int x){
    return x*x;
}

/// h[i]^2 + h[j]^2 - 2*h[i]*h[j] + dp[j] + c[i-1] - c[j];

void solve(){
    dp[1] = 0;
    Line_container cht;
    cht.add(Line(-2*h[1], sqr(h[1]) - c[1]));
    for(int i=2; i<=n; i++){
        dp[i] = -cht.get(h[i]) + sqr(h[i]) + c[i-1];
        cht.add(Line(-2*h[i], sqr(h[i]) + dp[i] - c[i]));
    }
    cout << dp[n];
}

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

    nhap();
    solve();

    return 0;
}
/**

6
3 8 7 1 6 6
0 -1 9 1 2 0

0 25 15

-6 + 9
-16 + 90
-14 + 56



**/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 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 50 ms 5468 KB Output is correct
2 Correct 50 ms 5780 KB Output is correct
3 Correct 50 ms 5456 KB Output is correct
4 Correct 48 ms 5468 KB Output is correct
5 Correct 49 ms 7248 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 50 ms 5468 KB Output is correct
7 Correct 50 ms 5780 KB Output is correct
8 Correct 50 ms 5456 KB Output is correct
9 Correct 48 ms 5468 KB Output is correct
10 Correct 49 ms 7248 KB Output is correct
11 Correct 44 ms 5516 KB Output is correct
12 Correct 51 ms 5468 KB Output is correct
13 Correct 29 ms 5464 KB Output is correct
14 Correct 50 ms 5468 KB Output is correct
15 Correct 85 ms 14768 KB Output is correct
16 Correct 52 ms 7344 KB Output is correct
17 Correct 16 ms 5456 KB Output is correct
18 Correct 17 ms 5504 KB Output is correct