제출 #106476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106476		CorneliuVadimTudor	Building Bridges (CEOI17_building)	C++14	100 / 100	134 ms	30968 KiB

building

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40