oj.uz

Submission #44659

# Submission time Handle Problem Language Result Execution time Memory
44659 2018-04-04T13:48:26 Z bogdan10bos Building Bridges (CEOI17_building) C++14
0 / 100
 69 ms 14636 KB 
#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)
    {
        if(st + 1 == dr)    return;
        aint[nod] = line(0LL, (LL)1e18);
        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(st + 1 == dr)    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(st + 1 == dr)    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(0);
    lichao.addValue(1e6);
    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

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];
                                 ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6520 KB Output is correct
2 Correct 6 ms 6764 KB Output is correct
3 Correct 7 ms 6780 KB Output is correct
4 Correct 8 ms 6860 KB Output is correct
5 Incorrect 7 ms 6952 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9876 KB Output is correct
2 Correct 66 ms 11064 KB Output is correct
3 Correct 64 ms 11940 KB Output is correct
4 Correct 69 ms 13032 KB Output is correct
5 Incorrect 66 ms 14636 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6520 KB Output is correct
2 Correct 6 ms 6764 KB Output is correct
3 Correct 7 ms 6780 KB Output is correct
4 Correct 8 ms 6860 KB Output is correct
5 Incorrect 7 ms 6952 KB Output isn't correct