oj.uz

Submission #161611

# Submission time Handle Problem Language Result Execution time Memory
161611 2019-11-03T09:58:27 Z Akashi Building Bridges (CEOI17_building) C++14
30 / 100
 48 ms 6524 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int n;
int h[N], w[N];
long long d[N];

struct node{
    long long a, b;
    node *left, *right;

    node(){
        a = b = 0;
        left = right = NULL;
    }
};

node *arb;
void update(long long a, long long b, int st = 1, int dr = n, node *nod = arb){
    if(st == dr){
        if(a + 1LL * b * st < nod->a + 1LL * nod->b * st){
            nod->a = a; nod->b = b;
        }
        return ;
    }

    int mij = (st + dr) / 2;
    if(a + 1LL * b * mij < nod->a + 1LL * nod->b * mij) swap(a, nod->a), swap(b, nod->b);

    if(b == nod->b && a >= nod->a) return ;

    if(b < nod->b){
        if(nod->right == NULL){
            nod->right = new node;
            nod->right->a = a; nod->right->b = b;
            return ;
        }
        update(a, b, mij + 1, dr, nod->right);
    }
    else{
        if(nod->left == NULL){
            nod->left = new node;
            nod->left->a = a; nod->left->b = b;
        }
        update(a, b, st, mij, nod->left);
    }
}

void query(long long &val, long long x, int st = 1, int dr = n, node *nod = arb){
    if(st > dr) return ;

    int mij = (st + dr) / 2;

    val = min(val, nod->a + 1LL * x * nod->b);

    if(x <= mij){
        if(nod->left == NULL) return ;
        query(val, x, st, mij, nod->left);
    }
    else{
        if(nod->right == NULL) return ;
        query(val, x, mij + 1, dr, nod->right);
    }
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i)
        scanf("%d", &h[i]), d[i] = -1e18;
    for(int i = 1; i <= n ; ++i)
        scanf("%d", &w[i]);

    d[1] = 0;
    arb = new node;
    arb->a = 1LL * h[1] * h[1] - w[1]; arb->b = -2LL * h[1];

    long long aux;
    for(int i = 2; i <= n ; ++i){
        w[i] += w[i - 1];

        aux = 1e18;
        query(aux, h[i]);

        d[i] = 1LL * h[i] * h[i] + w[i - 1] + aux;

        update(1LL * h[i] * h[i] + d[i] - w[i], -2LL * h[i]);
    }

    printf("%lld", d[n]);

    return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building.cpp:74:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &h[i]), d[i] = -1e18;
         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
building.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &w[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3320 KB Output is correct
2 Correct 48 ms 3320 KB Output is correct
3 Correct 48 ms 3324 KB Output is correct
4 Correct 44 ms 2936 KB Output is correct
5 Correct 48 ms 6524 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -