Submission #62710

#	Time	Username	Problem	Language	Result	Execution time	Memory
62710		eriksuenderhauf	Building Bridges (CEOI17_building)	C++11	100 / 100	89 ms	9960 KiB

building

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <fstream>
#define ni(n) scanf("%d", &n)
#define nl(n) scanf("%lld", &n)
#define nai(a,n) for (int i = 0; i < (n); i++) ni((a)[i])
#define nal(a,n) for (int i = 0; i < (n); i++) nl((a)[i])
#define case(t) printf("Case #%d: ", (t))
#define pii pair<int, int>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e18 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
using namespace std;
ll h[MAXN], w[MAXN], pre[MAXN], dp[MAXN];
bool q = false;

struct Line
{
    ll m, n;
    mutable double p;

    const bool operator<(Line rhs) const
    {
        return q ? p < rhs.p : m < rhs.m;
    }
};

struct Hull
{
    multiset<Line> lines;

    bool bad(multiset<Line>::iterator x, multiset<Line>::iterator y)
    {
        if (y == lines.end())
        {
            x->p = INF;
            return false;
        }
        if (x->m == y->m)
            x->p = x->n > y->n ? INF : -INF;
        else
            x->p = ((double) y->n - x->n) / ((double) x->m - y->m);
        return x->p >= y->p;
    }

    void add(ll m, ll n)
    {
        multiset<Line>::iterator z = lines.insert({m, n, 0});
        multiset<Line>::iterator y = z++;
        multiset<Line>::iterator x = y;
        while (bad(y, z))
            z = lines.erase(z);
        if (x != lines.begin() && bad(--x, y))
            bad(x, y = lines.erase(y));
        while ((y = x) != lines.begin() && (--x)->p >= y->p)
            bad(x, lines.erase(y));
    }

    ll query(ll x)
    {
        q = true;
        Line l = *lines.lower_bound({0, 0, x});
        q = false;
        return l.m * x + l.n;
    }
};

int main()
{
    int n;
    ni(n);
    nal(h, n);
    nal(w, n);
    for (int i = 1; i < n; i++)
        pre[i] = pre[i - 1] + w[i];
    Hull hu;
    hu.add(2 * h[0], -h[0] * h[0]);
    for (int i = 1; i < n; i++)
    {
        dp[i] = -hu.query(h[i]) + pre[i - 1] + h[i] * h[i];
        hu.add(2 * h[i], -dp[i] + pre[i] - h[i] * h[i]);
    }
    printf("%lld\n", dp[n - 1]);
    return 0;
}

Compilation message (stderr)

building.cpp: In member function 'll Hull::query(ll)':
building.cpp:76:46: warning: narrowing conversion of 'x' from 'll {aka long long int}' to 'double' inside { } [-Wnarrowing]
         Line l = *lines.lower_bound({0, 0, x});
                                              ^
building.cpp: In function 'int main()':
building.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &n)
               ~~~~~^~~~~~~~~~
building.cpp:85:5: note: in expansion of macro 'ni'
     ni(n);
     ^~
building.cpp:10:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define nl(n) scanf("%lld", &n)
               ~~~~~^~~~~~~~~~~~
building.cpp:12:48: note: in expansion of macro 'nl'
 #define nal(a,n) for (int i = 0; i < (n); i++) nl((a)[i])
                                                ^~
building.cpp:86:5: note: in expansion of macro 'nal'
     nal(h, n);
     ^~~
building.cpp:10:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define nl(n) scanf("%lld", &n)
               ~~~~~^~~~~~~~~~~~
building.cpp:12:48: note: in expansion of macro 'nl'
 #define nal(a,n) for (int i = 0; i < (n); i++) nl((a)[i])
                                                ^~
building.cpp:87:5: note: in expansion of macro 'nal'
     nal(w, n);
     ^~~

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