oj.uz

Submission #641953

# Submission time Handle Problem Language Result Execution time Memory
641953 2022-09-18T01:35:46 Z SirCovidThe19th Building Bridges (CEOI17_building) C++17
100 / 100
 97 ms 8408 KB 
#include <bits/stdc++.h>
using namespace std;
 
template<class T> struct lichao{
    struct line{
        T m, b;
        T operator()(T x){ return m * x + b; }
    };
    lichao(){ extend(0); extend(0); }
    const T lim = 1e18; vector<line> seg; vector<int> lc, rc;
    
    int extend(int i){
        if (i) return i;
        seg.push_back({0, lim}); lc.push_back(0); rc.push_back(0);
        return seg.size() - 1;
    }
    void upd(line S, int l = 0, int r = 1e6+5, int i = 1){
        if (S.b == lim) return;
        if (l == r){ seg[i] = (S(l) < seg[i](l)) ? S : seg[i]; return; }
        if (seg[i].m > S.m) swap(seg[i], S); 
 
        int mid = (l + r) / 2 - (l + r < 0 and (l + r) % 2);
        if (S(mid) < seg[i](mid)){
            swap(S, seg[i]);
            upd(S, mid + 1, r, rc[i] = extend(rc[i]));
        }
        else upd(S, l, mid, lc[i] = extend(lc[i]));
    }
    T qry(int x, int l = 0, int r = 1e6+5, int i = 1){
        if (x < l or x > r or !i) return lim;
        if (l == r) return seg[i](l);
        int mid = (l + r) / 2 - (l + r < 0 and (l + r) % 2);
        return min({seg[i](x), qry(x, l, mid, lc[i]), qry(x, mid + 1, r, rc[i])});
    }
};
 
int n; long long H[100005], pref[100005], dp[100005]; lichao<long long> lc;
 
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> H[i];
    for (int i = 1; i <= n; i++) cin >> pref[i], pref[i] += pref[i - 1];
 
    for (int i = 1; i <= n; i++){
        dp[i] = lc.qry(H[i]) + (H[i] * H[i] + pref[i - 1]);
        if (i == 1) dp[i] = 0;
        lc.upd({-2 * H[i], H[i] * H[i] + dp[i] - pref[i]});
    }
    cout<<dp[n]<<"\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3172 KB Output is correct
2 Correct 80 ms 3140 KB Output is correct
3 Correct 85 ms 3112 KB Output is correct
4 Correct 75 ms 2752 KB Output is correct
5 Correct 71 ms 5704 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 82 ms 3172 KB Output is correct
7 Correct 80 ms 3140 KB Output is correct
8 Correct 85 ms 3112 KB Output is correct
9 Correct 75 ms 2752 KB Output is correct
10 Correct 71 ms 5704 KB Output is correct
11 Correct 97 ms 5940 KB Output is correct
12 Correct 87 ms 6000 KB Output is correct
13 Correct 81 ms 3264 KB Output is correct
14 Correct 92 ms 6096 KB Output is correct
15 Correct 73 ms 8408 KB Output is correct
16 Correct 68 ms 5712 KB Output is correct
17 Correct 68 ms 2632 KB Output is correct
18 Correct 66 ms 2568 KB Output is correct