oj.uz

Submission #477335

# Submission time Handle Problem Language Result Execution time Memory
477335 2021-10-01T17:02:06 Z XBoRickie Building Bridges (CEOI17_building) C++11
100 / 100
 315 ms 9488 KB 
#include <bits/stdc++.h>
using namespace std;
// Typedef
typedef long double                ld;
typedef long long int              int64;
typedef unsigned long long int     uint64;
typedef std::pair<int, int>        PLL;
typedef std::pair<int64, int64>    PII;
typedef std::vector<int>           VI;
typedef std::vector<long long>     VLL;
// Define For-loop
#define FOR(i, j, k, in)           for (int i = (j); i < (k) ; i += (in))
#define FORW(i, j, k, in)          for (int i = (j); i <= (k); i += (in))
#define RFOR(i, j, k, in)          for (int i = (j); i >= (k); i -= (in))
// Define Data structure func
#define all(cont)                  cont.begin(), cont.end()
#define rall(cont)                 cont.rbegin(), cont.rend()
#define sz(cont)                   int((cont).size())
#define pb                         push_back
#define mp                         make_pair
#define fi                         first
#define se                         second
// Define number
#define IINF                       0x3f3f3f3f
#define LLINF                      1000111000111000111LL
#define PI                         3.1415926535897932384626433832795
// Other
#define elif                       else if
#define lend                       '\n'
#define hardio(name)               freopen(name".inp","r",stdin), freopen(name".out","w",stdout);
void FastIO() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);  }

const int MOD = 1e9 + 7, MOD2 = 1e9 + 9;
// ======================================================================

int64 h[100006], pf[100006] = {};
int64 dp[100006] = {};
int sqN = 0, n;

struct CVH {
    vector<PII> lines;
    double intersect(PII& l, PII& r) {
        return (1.0*(l.se - r.se))/(1.0*(r.fi - l.fi));
    }
    bool bad(PII& a, PII& b, PII& c) {
        return intersect(a, c) <= intersect(b, a);
    }
    void addLine(PII line, bool flag) {
        if (flag) {
            while (sz(lines) >= 2 && bad(lines[sz(lines) - 2], lines[sz(lines) - 1], line)) lines.pop_back();
            if (sz(lines) == 1 && lines[0].fi == line.fi) lines.pop_back();
            lines.pb(line);
        } else {
            lines.pb(line);
            RFOR(i, sz(lines) - 1, 1, 1) {
                if (lines[i - 1] <= lines[i]) swap(lines[i - 1], lines[i]);
                else break;
            }
        }
    }
    int64 query(int64 x) {
        int l = 0, r = sz(lines) - 1, m, best = -1;
        while (l <= r) {
            m = (l + r) >> 1;
            double pos = m > 0 ? intersect(lines[m], lines[m - 1]) : -IINF;
            if (pos <= x) best = m, l = m + 1;
            else r = m - 1;
        }
        return best == -1 ? IINF : lines[best].fi * x + lines[best].se;
    }
} off, aux, pil;

void Clear_Stack() {
    aux.lines.clear();
    int esq = 0, dir = 0;
    while(esq < sz(off.lines) && dir < sz(pil.lines)) {
        if(off.lines[esq] >= pil.lines[dir]) aux.addLine(off.lines[esq], 1), ++esq;
        else aux.addLine(pil.lines[dir], 1), dir++;
    }
    while(esq < sz(off.lines)) aux.addLine(off.lines[esq], 1), ++esq;
    while(dir < sz(pil.lines)) aux.addLine(pil.lines[dir], 1), ++dir;
    off.lines = aux.lines, pil.lines.clear(), aux.lines.clear();
}

int main(int argc, char* argv[]) {
    FastIO();

    cin >> n; sqN = sqrt(n);
    FORW(i, 1, n, 1) cin >> h[i];
    FORW(i, 1, n, 1) cin >> pf[i], pf[i] += pf[i - 1];

    dp[1] = 0;
    pil.addLine(PII(-2ll * h[1], 1ll * h[1] * h[1] - pf[1]), 0);

    FORW(i, 2, n, 1) {
        int64 x = off.query(h[i]);
        for(auto& u : pil.lines) x = min(x, u.fi * h[i] + u.se);
        dp[i] = x + h[i] * h[i] + pf[i - 1];
        pil.addLine(PII(-2ll * h[i], 1ll * h[i] * h[i] - pf[i] + dp[i]), 0);
        if (sz(pil.lines) >= sqN) Clear_Stack();
    }

    cout << dp[n] << endl;


    return 0; }

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 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 83 ms 2724 KB Output is correct
2 Correct 81 ms 2756 KB Output is correct
3 Correct 84 ms 2640 KB Output is correct
4 Correct 78 ms 2596 KB Output is correct
5 Correct 96 ms 3396 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 83 ms 2724 KB Output is correct
7 Correct 81 ms 2756 KB Output is correct
8 Correct 84 ms 2640 KB Output is correct
9 Correct 78 ms 2596 KB Output is correct
10 Correct 96 ms 3396 KB Output is correct
11 Correct 81 ms 2648 KB Output is correct
12 Correct 83 ms 3668 KB Output is correct
13 Correct 67 ms 3776 KB Output is correct
14 Correct 83 ms 3812 KB Output is correct
15 Correct 315 ms 9488 KB Output is correct
16 Correct 97 ms 4344 KB Output is correct
17 Correct 80 ms 3696 KB Output is correct
18 Correct 82 ms 3636 KB Output is correct