oj.uz

답안 #972129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972129 2024-04-30T06:42:29 Z efedmrlr Building Bridges (CEOI17_building) C++17
30 / 100
 53 ms 10684 KB 
#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const lli INF = 1e17;

struct Line {
    lli a, b;
    Line() {}
    Line(lli aa, lli bb) : a(aa), b(bb) {}
    ld intersect(Line &oth) {
        return (ld)(oth.b - b) / (a - oth.a);
    }
    lli eval(int x) {
        return a * x + b;
    }
    bool operator<(Line &oth) {
        return a < oth.a;
    }
    
    void print() {
        cout << a << " x + " << b << "\n";
    }
};

struct Node {
    Line x;
    int lc, rc;
    Node() : x(Line(0, INF)), lc(-1), rc(-1) {}
};

struct LiChao {
    const int MX = 1e6 + 5;
    vector<Node> st;
    int pt;
    int create_node() {
        st.pb(Node()); 
        return pt++;
    }
    void reset() {
        pt = 0;
        st.clear();
        create_node();
    }
    void extend(int v) {
        if(st[v].lc == -1) st[v].lc = create_node();
        if(st[v].rc == -1) st[v].rc = create_node();
    } 
    void update(int tl, int tr, int v, Line nw) {
        if(nw.a == st[v].x.a) {
            if(nw.b < st[v].x.b) {
                swap(nw, st[v].x);
            }
            return;
        }
        if(tl == tr) {
            if(nw.eval(tl) < st[v].x.eval(tl)) {
                st[v].x = nw;
            }
            return;
        } 
        extend(v);
        int tm = (tl + tr) >> 1;
        if(nw.a > st[v].x.a) {
            swap(nw, st[v].x);
        } 
        ld inter = nw.intersect(st[v].x);
        if(inter < (ld)tm) {
            swap(st[v].x, nw);
            update(tl, tm, st[v].lc, nw);
        }
        else {
            update(tm + 1, tr, st[v].rc, nw);
        }
    }
    void update(Line nw) {
        // nw.print();
        update(0, MX, 0, nw);
    }
    lli query(int tl, int tr, int v, int ind) {
        if(tl == tr) {
            return st[v].x.eval(ind);
        }
        int tm = (tl + tr) >> 1;
        extend(v);
        if(ind <= tm) {
            return min(query(tl, tm, st[v].lc, ind), st[v].x.eval(ind));
        } 
        else {
            return min(query(tm + 1, tr, st[v].rc, ind), st[v].x.eval(ind));
        }
    }
    lli query(int ind) {
        return query(0, MX, 0, ind);
    }

};
LiChao st;
vector<int> h(N), w(N);
vector<lli> dp(N, INF), pr(N, 0);
void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for(int i = 1; i <= n; i++) {
        pr[i] = pr[i - 1] + w[i];
    }
    dp[1] = 0;
    st.reset();
    st.update(Line(-2 * h[1], h[1] * h[1] - pr[1] + dp[1]));
    for(int i = 2; i <= n; i++) {
        dp[i] = st.query(h[i]) + pr[i - 1] + h[i] * h[i];
        st.update(Line(-2 * h[i], h[i] * h[i] - pr[i] + dp[i]));
    }
    cout << dp[n];
}

signed main() {
    fastio();
    solve();
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 3060 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 10684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 3060 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Incorrect 53 ms 10684 KB Output isn't correct
7 Halted 0 ms 0 KB -