Submission #44661

#	Time	Username	Problem	Language	Result	Execution time	Memory
44661		bogdan10bos	Building Bridges (CEOI17_building)	C++14	100 / 100	107 ms	17376 KiB

building

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

class LiChao
{
public:
    int N, val[100005];
    int mp[1000005];

    struct line
    {
        LL x, y;
        line() { x = y = 0; }
        line(LL _x, LL _y) { x = _x; y = _y; }
    };

    line aint[400005];

    LL F(LL x, line l)
    {
        return l.x * x + l.y;
    }

    void addValue(int x)
    {
        if(mp[x]) return;
        mp[x] = 1;
        val[++N] = x;
    }

    void B(int nod, int st, int dr)
    {
        aint[nod] = line(0LL, (LL)1e18);
        if( dr - st <= 1 )    return;
        int mij = st + (dr - st) / 2;
        B(nod * 2, st, mij);
        B(nod * 2 + 1, mij, dr);
    }

    void init()
    {
        sort(val + 1, val + N + 1);
        for(int i = 1; i <= N; i++)
            mp[ val[i] ] = i;
        B(1, 1, N);
    }

    void U(int nod, int st, int dr, line l)
    {
        int mij = st + (dr - st) / 2;
        bool mj = F(val[mij], l) < F(val[mij], aint[nod]);
        bool lft = F(val[st], l) < F(val[st], aint[nod]);
        if(mj)  swap(aint[nod], l);
        if( dr - st <= 1 )    return;
        if(mj == lft)   U(nod * 2 + 1, mij, dr, l);
        else    U(nod * 2, st, mij, l);
    }

    void update(LL x, LL y)
    {
        line l(x, y);
        U(1, 1, N, l);
    }

    LL Q(int nod, int st, int dr, int x)
    {
        if( dr - st <= 1 )    return F(val[x], aint[nod]);
        LL v = F(val[x], aint[nod]);
        int mij = st + (dr - st) / 2;
        if(x <= mij)    return min(v, Q(nod * 2, st, mij, x));
        return min(v, Q(nod * 2 + 1, mij, dr, x));
    }

    LL get(LL x)
    {
        return Q(1, 1, N, mp[x]);
    }
};
LiChao lichao;

int N;
int h[100005];
LL dp[100005], sum[100005];

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d", &N);
    lichao.addValue(-1);
    lichao.addValue(1e6 + 1);
    for(int i = 1; i <= N; i++) scanf("%d", &h[i]), lichao.addValue(h[i]);
    for(int i = 1; i <= N; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];

    lichao.init();
    dp[1] = 0;
    for(int i = 1; i <= N; i++)
    {
        if(i != 1)
            dp[i] = lichao.get(h[i]) + 1LL * h[i] * h[i] + sum[i - 1];
        lichao.update(-2 * h[i], 1LL * h[i] * h[i] + dp[i] - sum[i]);
    }
    printf("%lld\n", dp[N]);

    return 0;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
building.cpp:100:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d", &h[i]), lichao.addValue(h[i]);
                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:101:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
                                 ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:31:16: warning: array subscript is below array bounds [-Warray-bounds]
         if(mp[x]) return;
            ~~~~^
building.cpp:32:13: warning: array subscript is below array bounds [-Warray-bounds]
         mp[x] = 1;
         ~~~~^

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