Submission #1296767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296767		khoile08	Building Bridges (CEOI17_building)	C++20	100 / 100	41 ms	18440 KiB

building

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
//#define int long long
#define fi first
#define se second
#define ll long long
#define db double 
#define pb push_back
#define ii pair<int,int>
#define sq(i) (1LL * (i) * (i))
#define MASK(i) (1LL << i)
#define task "task"

const int inf = 1e9;
const ll INF = 1e18;
const int N = 1e5 + 4;
const int M = 1e6 + 4;

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

struct Line {
    ll a, b;
    Line(ll _a = 0, ll _b = 0) {
        a = _a;
        b = _b;
    }

    ll cal(ll x) {
        return a * x + b;
    }
};

struct Lichao {
    Line tr[M];

    void init() {
        FOR(i, 0, M - 4) tr[i] = Line(0, INF); 
    }

    void upd(int l, int r, Line f) {
        if(l > r) return;
        int mid = l + r >> 1;
        if(l == r) {
            if(tr[mid].cal(l) > f.cal(l)) tr[mid] = f;
            return;
        }
        if(tr[mid].cal(mid) > f.cal(mid)) swap(tr[mid], f);
        if(tr[mid].cal(l) > f.cal(l)) upd(l, mid - 1, f);
        if(tr[mid].cal(r) > f.cal(r)) upd(mid + 1, r, f);
    }

    ll get(int l, int r, int pos) {
        if(l > r) return INF;
        int mid = l + r >> 1;
        ll ret = tr[mid].cal(pos);
        if(pos == mid) return ret;
        if(pos < mid) return min(ret, get(l, mid - 1, pos));
        if(pos > mid) return min(ret, get(mid + 1, r, pos));
    }
} lch;

ll dp[N];

void Solve() {
    lch.init();
    lch.upd(0, M - 4, Line(-2 * h[1], sq(h[1]) - pre[1]));

    FOR(i, 2, n) {
        dp[i] = lch.get(0, M - 4, h[i]) + pre[i - 1] + sq(h[i]);
        lch.upd(0, M - 4, Line(-2 * h[i], sq(h[i]) - pre[i] + dp[i]));
    } 
    cout << dp[n] << '\n';
}

signed main() {
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout); 
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--) {
        cin >> n;
        FOR(i, 1, n) cin >> h[i];
        FOR(i, 1, n) {
            cin >> w[i];
            pre[i] = pre[i - 1] + w[i];
        } 
        Solve();
    }
}

Compilation message (stderr)

building.cpp: In member function 'long long int Lichao::get(int, int, int)':
building.cpp:64:5: warning: control reaches end of non-void function [-Wreturn-type]
   64 |     }
      |     ^
building.cpp: In function 'int main()':
building.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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