oj.uz

Submission #886636

# Submission time Handle Problem Language Result Execution time Memory
886636 2023-12-12T13:43:48 Z dwuy Building Bridges (CEOI17_building) C++14
100 / 100
 111 ms 15656 KB 
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 200005;

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 m < other.m;
        const Line *nxt = succ();
        if(!nxt) return 0;
        int x = other.m;
        return b - nxt->b < (nxt->m - m)*x;
    }
};

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 = -line.m;
        line.b = -line.b;
        auto itr = insert(line);
        itr->succ = [ = ]{ return next(itr) == end()? 0 : &*next(itr); };
        if(bad(itr)){
            erase(itr);
            return;
        }
        while(next(itr)!=end() && bad(next(itr))) erase(next(itr));
        while(itr!=begin() && bad(prev(itr))) erase(prev(itr));
    }

    int get(int x){
        if(empty()) return 0;
        auto itr = lower_bound(Line(x, OO));
        return itr->m*x + itr->b;
    }
};

int n;
int h[MX];
int w[MX];
int f[MX];
int sum[MX];

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

void solve(){
    Line_Container cht;
    cht.add(Line(-2*h[1], h[1]*h[1] - sum[1]));
    for(int i=2; i<=n; i++){
        f[i] = -cht.get(h[i]) + h[i]*h[i] + sum[i-1];
        cht.add(Line(-2*h[i], f[i] + h[i]*h[i] - sum[i]));
    }
    cout << f[n];
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

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 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 52 ms 6604 KB Output is correct
2 Correct 50 ms 6488 KB Output is correct
3 Correct 50 ms 6492 KB Output is correct
4 Correct 43 ms 6236 KB Output is correct
5 Correct 66 ms 8440 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 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 52 ms 6604 KB Output is correct
7 Correct 50 ms 6488 KB Output is correct
8 Correct 50 ms 6492 KB Output is correct
9 Correct 43 ms 6236 KB Output is correct
10 Correct 66 ms 8440 KB Output is correct
11 Correct 44 ms 6748 KB Output is correct
12 Correct 51 ms 6488 KB Output is correct
13 Correct 30 ms 6492 KB Output is correct
14 Correct 48 ms 6740 KB Output is correct
15 Correct 111 ms 15656 KB Output is correct
16 Correct 63 ms 8276 KB Output is correct
17 Correct 17 ms 6488 KB Output is correct
18 Correct 17 ms 6384 KB Output is correct