Submission #162255

#	Time	Username	Problem	Language	Result	Execution time	Memory
162255		karma	Building Bridges (CEOI17_building)	C++14	100 / 100	275 ms	129160 KiB

building

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(1e5) + 7;
const ll Cmax = (ll)1e18;
typedef pair<int, int> pii;

struct line {
    ll a, b;
    line (ll a = 0, ll b = Cmax): a(a), b(b) {}
    ll GetVal(ll x) {return a * x + b;}
};

struct TSegment {
    int l, r, mid;
    line cur;
    TSegment* left;
    TSegment* right;
    TSegment (int l = 0, int r = 0): l(l), r(r) {
        mid = (l + r) >> 1;
        cur = line();
        if(l == r) {
            left = right = NULL;
            return;
        }
        left = new TSegment(l, mid);
        right = new TSegment(mid + 1, r);
    }
    void Update(int x, int y, line val) {
        if(l > y || r < x) return;
        if(x <= l && r <= y) {
            ll lcur = cur.GetVal(l);
            ll rcur = cur.GetVal(r);
            ll lval = val.GetVal(l);
            ll rval = val.GetVal(r);
            if(lcur >= lval && rcur >= rval) {cur = val; return;}
            if(lcur <= lval && rcur <= rval) return;
            ll mval = val.GetVal(mid);
            ll mcur = cur.GetVal(mid);
            if(lcur >= lval && mcur >= mval) {
                right -> Update(x, y, cur);
                cur = val; return;
            }
            if(lcur <= lval && mcur <= mval) {
                right -> Update(x, y, val);
                return;
            }
            if(mcur >= mval && rcur >= rval) {
                left -> Update(x, y, cur);
                cur = val; return;
            }
            if(mcur <= mval && rcur <= rval) {
                left -> Update(x, y, val);
                return;
            }
        }
        left -> Update(x, y, val);
        right -> Update(x, y, val);
    }
    ll Query(int x) {
        if(l > x || r < x) return Cmax;
        ll res = cur.GetVal(x);
        if(l == r) return res;
        res = min(res, left -> Query(x));
        res = min(res, right -> Query(x));
        return res;
    }
};

int n;
ll w[N], h[N], f[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> w[i], w[i] += w[i - 1];
    TSegment Min = TSegment(0, int(1e6));
    Min.Update(0, 1e6, line(-2 * h[1], f[1] - w[1] + h[1] * h[1]));
    for(int i = 2; i <= n; ++i) {
        f[i] = Min.Query(h[i]) + h[i] * h[i] + w[i - 1];
        Min.Update(0, 1e6, line(-2 * h[i], f[i] - w[i] + h[i] * h[i]));
    }
    cout << f[n];
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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