oj.uz

Submission #106476

# Submission time Handle Problem Language Result Execution time Memory
106476 2019-04-18T18:05:15 Z CorneliuVadimTudor Building Bridges (CEOI17_building) C++14
100 / 100
 134 ms 30968 KB 
#include <bits/stdc++.h>

const int MAXN = 1e5;
const long long INF = 1e18;

int h[1 + MAXN], w[1 + MAXN];
long long d[1 + MAXN];

class Batch{
private:
    struct Line{
        long long a, b;
        inline long long get(long long x) {
            return 1LL * a * x + b;
        }
    };
    struct LiChao{
        LiChao *st, *dr;
        Line l;
        LiChao(){
            st = dr = NULL;
            l = {0, INF};
        }
    }*root;


public:
    Batch() {root = new LiChao();}

    inline void fix(LiChao *nod) {
        if(nod -> st == NULL) nod -> st = new LiChao();
        if(nod -> dr == NULL) nod -> dr = new LiChao();
    }

    void add(LiChao *nod, long long left, long long right, Line l) {
        fix(nod);
        Line &curr = nod -> l;
        if(l.get(left) <= curr.get(left) && l.get(right) <= curr.get(right)){curr = l; return;}
        if(l.get(left) >= curr.get(left) && l.get(right) >= curr.get(right)) return;

        long long mid = (left + right) / 2;
        if(curr.get(left) > l.get(left))
            std::swap(l, curr);
        if(curr.get(mid) > l.get(mid)){
            std::swap(l, curr);
            add(nod -> st, left, mid, l);
        }
        else add(nod -> dr, mid + 1, right, l);
    }

    long long query(LiChao *nod, long long left, long long right, long long x) {
        fix(nod);
        long long val = nod -> l.get(x);
        if(left == right) return val;

        long long mid = (left + right) / 2;
        if(x <= mid) return std::min(val, query(nod -> st, left, mid, x));
        return std::min(val, query(nod -> dr, mid + 1, right, x));
    }

    void add(Line l){add(root, 0, 1e9, l);}
    long long query(long long x){return query(root, 0, 1e9, x);}
};

int main(){
    FILE*fi,*fo;
    //fi = fopen("a.in","r");
    //fo = fopen("a.out","w");
    fi = stdin;
    fo = stdout;

    int n;
    fscanf(fi,"%d", &n);
    for(int i = 1; i <= n; i++)
        fscanf(fi,"%d", &h[i]);

    long long sum = 0;
    for(int i = 1; i <= n; i++) {
        fscanf(fi,"%d", &w[i]);
        sum += w[i];
    }

    /*
    d[i] = d[j] + (h[i] - h[j])^2 + sum(k = j + 1, i - 1)w[i]
    d[i] = -2h[j] * h[i] + (h[j] * h[j] + d[j]) + h[i] * h[i] - w[i] + sum(k = j + 1, i - 1)w[i]
    */
    Batch hull;
    hull.add({-2 * h[1], 1LL * h[1] * h[1] - w[1]});
    for(int i = 2; i <= n; i++) {
        d[i] = hull.query(h[i]) + 1LL * h[i] * h[i] - w[i];
        hull.add({-2 * h[i], 1LL * h[i] * h[i] + d[i]});
    }
    fprintf(fo,"%lld", d[n] + sum);
    return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:73:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fi,"%d", &n);
     ~~~~~~^~~~~~~~~~~~~
building.cpp:75:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fi,"%d", &h[i]);
         ~~~~~~^~~~~~~~~~~~~~~~
building.cpp:79:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fi,"%d", &w[i]);
         ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 4392 KB Output is correct
2 Correct 77 ms 4472 KB Output is correct
3 Correct 78 ms 4380 KB Output is correct
4 Correct 65 ms 3192 KB Output is correct
5 Correct 88 ms 23544 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 75 ms 4392 KB Output is correct
7 Correct 77 ms 4472 KB Output is correct
8 Correct 78 ms 4380 KB Output is correct
9 Correct 65 ms 3192 KB Output is correct
10 Correct 88 ms 23544 KB Output is correct
11 Correct 134 ms 17704 KB Output is correct
12 Correct 125 ms 17632 KB Output is correct
13 Correct 58 ms 3380 KB Output is correct
14 Correct 131 ms 17656 KB Output is correct
15 Correct 93 ms 30968 KB Output is correct
16 Correct 82 ms 23464 KB Output is correct
17 Correct 34 ms 3064 KB Output is correct
18 Correct 58 ms 2936 KB Output is correct