oj.uz

Submission #417463

# Submission time Handle Problem Language Result Execution time Memory
417463 2021-06-03T18:32:37 Z JerryLiu06 Building Bridges (CEOI17_building) C++17
100 / 100
 133 ms 12848 KB 
#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

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.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 3788 KB Output is correct
2 Correct 87 ms 3740 KB Output is correct
3 Correct 87 ms 3680 KB Output is correct
4 Correct 84 ms 3496 KB Output is correct
5 Correct 81 ms 5372 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 88 ms 3788 KB Output is correct
7 Correct 87 ms 3740 KB Output is correct
8 Correct 87 ms 3680 KB Output is correct
9 Correct 84 ms 3496 KB Output is correct
10 Correct 81 ms 5372 KB Output is correct
11 Correct 82 ms 3808 KB Output is correct
12 Correct 90 ms 3780 KB Output is correct
13 Correct 57 ms 3652 KB Output is correct
14 Correct 86 ms 3908 KB Output is correct
15 Correct 133 ms 12848 KB Output is correct
16 Correct 80 ms 5444 KB Output is correct
17 Correct 27 ms 3652 KB Output is correct
18 Correct 24 ms 3604 KB Output is correct