oj.uz

답안 #169266

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
169266 2019-12-19T11:58:30 Z kostia244 Building Bridges (CEOI17_building) C++17
0 / 100
 163 ms 66424 KB 
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
struct func {
    ll k, b;
    func(ll k = 0, ll b = 1e18) :k(k), b(b){
    }
    ll operator()(ll x) {
        return k*x+b;
    }
};
const int maxn = 1e6 + 55;
func tree[4*maxn];
void upd(int v, int l, int r, func f) {
    // cout << v << " " << l << " " << r << "\n";
    int m = (l+r)>>1;
    int L = f(l) < tree[v](l);
    int M = f(m) < tree[v](m);
    if(M) {
        swap(f, tree[v]);
    }
    if(r-l<2) return;

    if(L!=M)
        upd(v<<1, l, m, f);
    else
        upd(v<<1|1, m, r, f);
}
ll get(int v, int l, int r, int x) {
    ll m = (l+r)>>1;
    if(r-l<2) return tree[v](x);
    if(v<m)
        return min(tree[v](x), get(v<<1, l, m, x));
    else
        return min(tree[v](x), get(v<<1|1, m, r, x));
}
void add(func f) {
    upd(1, 0, 1e6 + 1, f);
}
ll get(ll x) {
    return get(1, 0, 1e6 + 1, x);
}
ll n, h[maxn], w[maxn], pref[maxn];
int main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        pref[i] = pref[i-1]+w[i];
    }
    ll t = 0;
    add(func(-2*h[1], h[1]*h[1]-pref[1]));
    // return 0;
    for(int i = 2; i <= n; i++) {
        t = get(h[i]) + h[i]*h[i] + pref[i-1];
        add(func(-2*h[i], t + h[i]*h[i] - pref[i]));
    }
    cout << t;
}

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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