Submission #1245247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245247		Mike_Vu	Building Bridges (CEOI17_building)	C++17	0 / 100	36 ms	17224 KiB

building

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(j) (1LL<<(j))
#define ALL(v) v.begin(), v.end()

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct Line{
    ll a, b;
    Line(ll _a = 0, ll _b = LLONG_MAX) {
        a = _a;
        b = _b;
    }
    ll cal(ll x) {
        return a*x+b;
    }
};
struct LICHAO{
    vector<Line> tr;
    void init(int sz) {
        tr.assign(sz+1, Line());
    }
    //id = mid
    void update(Line cur, int l, int r) {
        if (l > r) return;
        int mid = (l+r)>>1;
        if (tr[mid].cal(mid) > cur.cal(mid)) swap(tr[mid], cur);
        if (l == r) return;
        if (tr[mid].a < cur.a) {
            update(cur, l, mid-1);
        }
        if (tr[mid].a > cur.a) {
            update(cur, mid+1, r);
        }
    }
    ll query(ll x, int l, int r) {
        if (l > r) return LLONG_MAX;
        int mid = (l+r)>>1;
        ll val = tr[mid].cal(x);
        if (x == mid) return val;
        if (x < mid) return min(val, query(x, l, mid-1));
        if (x > mid) return min(val, query(x, mid+1, r));
    }
};

const int maxn = 1e5+5, maxval = 1e6+5;
int n, a[maxn];
ll ps[maxn];
LICHAO tr;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    ps[0] = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        ps[i] = ps[i-1]+x;
    }
    tr.init(maxval);
    //initiate state
    tr.update(Line(-2*a[1], (ll)a[1]*a[1]-ps[1]), 1, maxval);
    for (int i = 1; i <= n; i++) {
        ll dp = tr.query(a[i], 1, maxval)+(ll)a[i]*a[i]+ps[i-1];
        if (i == n) {
            cout << dp;
            return 0;
        }
        tr.update(Line(-2*a[i], (ll)a[i]*a[i]-ps[i]+dp), 1, maxval);
    }
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

Compilation message (stderr)

building.cpp: In member function 'll LICHAO::query(ll, int, int)':
building.cpp:58:5: warning: control reaches end of non-void function [-Wreturn-type]
   58 |     }
      |     ^

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40