oj.uz

Submission #44661

# Submission time Handle Problem Language Result Execution time Memory
44661 2018-04-04T14:09:35 Z bogdan10bos Building Bridges (CEOI17_building) C++14
100 / 100
 107 ms 17376 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)
    {
        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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6520 KB Output is correct
2 Correct 6 ms 6628 KB Output is correct
3 Correct 6 ms 6704 KB Output is correct
4 Correct 7 ms 6720 KB Output is correct
5 Correct 7 ms 6756 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 8728 KB Output is correct
2 Correct 68 ms 8792 KB Output is correct
3 Correct 71 ms 8944 KB Output is correct
4 Correct 59 ms 8944 KB Output is correct
5 Correct 105 ms 9548 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6520 KB Output is correct
2 Correct 6 ms 6628 KB Output is correct
3 Correct 6 ms 6704 KB Output is correct
4 Correct 7 ms 6720 KB Output is correct
5 Correct 7 ms 6756 KB Output is correct
6 Correct 77 ms 8728 KB Output is correct
7 Correct 68 ms 8792 KB Output is correct
8 Correct 71 ms 8944 KB Output is correct
9 Correct 59 ms 8944 KB Output is correct
10 Correct 105 ms 9548 KB Output is correct
11 Correct 97 ms 10572 KB Output is correct
12 Correct 107 ms 11692 KB Output is correct
13 Correct 56 ms 12168 KB Output is correct
14 Correct 95 ms 14000 KB Output is correct
15 Correct 66 ms 15512 KB Output is correct
16 Correct 72 ms 16008 KB Output is correct
17 Correct 32 ms 16300 KB Output is correct
18 Correct 31 ms 17376 KB Output is correct