Submission #417463

#	Time	Username	Problem	Language	Result	Execution time	Memory
417463		JerryLiu06	Building Bridges (CEOI17_building)	C++17	100 / 100	133 ms	12848 KiB

building

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define EACH(a,x) for (auto& a: x)
 
const int MOD = 1e9 + 7;
const int MX = 1e5 + 10; 
const ll INF = 1e18; 

// Description: Line Container where you can add lines of the form kx + m, and query maximum
// values at points x. *Useful for dynamic programming (CHT)* Time: O(lg N)

struct Line {
    bool type; ld X; ll M, C;

    bool operator<(const Line& L) const {
        if (type || L.type) return X < L.X; return M > L.M;
    }
};

struct LineContainer: set<Line> {
    bool hasPrev(set<Line>::iterator IT) { return IT != bg(); }

    bool hasNext(set<Line>::iterator IT) { return IT != end() && next(IT) != end(); }

    ld isect(set<Line>::iterator IT1, set<Line>::iterator IT2) {
        return (ld) (IT1 -> C - IT2 -> C) / (ld) (IT2 -> M - IT1 -> M);
    }
    void update(set<Line>::iterator IT) {
        if (hasPrev(IT)) { Line L = *IT; L.X = isect(prev(IT), IT); insert(erase(IT), L); }
    }
    bool BAD(set<Line>::iterator IT) {
        if (hasNext(IT) && next(IT) -> C <= IT -> C) return true;

        return (hasPrev(IT) && hasNext(IT) && isect(prev(IT), next(IT)) <= isect(prev(IT), IT));
    }
    void addLine(ll _M, ll _C) {
        set<Line>::iterator IT; IT = lb({0, 0, _M, _C});

        if (IT != end() && IT -> M == _M) {
            if (IT -> C <= _C) return ; erase(IT);
        }
        IT = insert({0, 0, _M, _C}).f; if (BAD(IT)) { erase(IT); return ; }

        while (hasPrev(IT) && BAD(prev(IT))) erase(prev(IT));
        while (hasNext(IT) && BAD(next(IT))) erase(next(IT));

        if (hasNext(IT)) update(next(IT)); update(IT);
    }
    ll QUERY(ll _X) {
        Line L = *prev(ub({1, (ld) _X, 0, 0})); return L.M * _X + L.C;
    }
};

int N; ll H[MX], W[MX], tot; ll DP[MX]; LineContainer CHT;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N; FOR(i, 1, N + 1) cin >> H[i]; FOR(i, 1, N + 1) cin >> W[i], tot += W[i];

    DP[1] = -W[1]; FOR(i, 2, N + 1) { 
        CHT.addLine(-2 * H[i - 1], DP[i - 1] + H[i - 1] * H[i - 1]);

        DP[i] = CHT.QUERY(H[i]) - W[i] + H[i] * H[i];
    }
    cout << tot + DP[N];
}

Compilation message (stderr)

building.cpp: In member function 'bool Line::operator<(const Line&) const':
building.cpp:56:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   56 |         if (type || L.type) return X < L.X; return M > L.M;
      |         ^~
building.cpp:56:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   56 |         if (type || L.type) return X < L.X; return M > L.M;
      |                                             ^~~~~~
building.cpp: In member function 'void LineContainer::addLine(ll, ll)':
building.cpp:80:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   80 |             if (IT -> C <= _C) return ; erase(IT);
      |             ^~
building.cpp:80:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   80 |             if (IT -> C <= _C) return ; erase(IT);
      |                                         ^~~~~
building.cpp:87:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   87 |         if (hasNext(IT)) update(next(IT)); update(IT);
      |         ^~
building.cpp:87:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   87 |         if (hasNext(IT)) update(next(IT)); update(IT);
      |                                            ^~~~~~

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