Submission #168221

#	Time	Username	Problem	Language	Result	Execution time	Memory
168221		mhy908	Building Bridges (CEOI17_building)	C++14	100 / 100	99 ms	14032 KiB

building

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int n;
LL h[1000010], w[1000010];
LL sum[1000010], dp;
struct DYNAMIC_Li_Chao{
    typedef long long LL;
    const LL inf=987654321987654321;
    struct NODE {
        LL st, fin;
        int l, r;
        LL a, b;
    };
    vector<NODE> tree;
    int newNode(LL aa, LL bb) {
        NODE temp;
        temp.st=aa;
        temp.fin=bb;
        temp.a=0;
        temp.b=-inf;
        temp.l=0;
        temp.r=0;
        tree.push_back(temp);
        return tree.size()-1;
    }
    LL findf(int point, LL num)
    {
        if(tree[point].st==tree[point].fin)return tree[point].a*num+tree[point].b;
        if(num<=(tree[point].st+tree[point].fin)/2)return max(tree[point].a*num+tree[point].b, tree[point].l?findf(tree[point].l, num):-inf);
        else return max(tree[point].a*num+tree[point].b, tree[point].r?findf(tree[point].r, num):-inf);
    }
    void in_LICHAO(int point, LL aa, LL bb)
    {
        LL mid=(tree[point].st+tree[point].fin)/2;
        LL fr=tree[point].a*tree[point].st+tree[point].b;
        LL re=tree[point].a*tree[point].fin+tree[point].b;
        LL nfr=aa*tree[point].st+bb;
        LL nre=aa*tree[point].fin+bb;
        if(fr>=nfr&&re>=nre)return;
        if(fr<=nfr&&re<=nre){
            tree[point].a=aa;
            tree[point].b=bb;
            return;
        }
        int templ, tempr;
        if(!tree[point].l){
            templ=newNode(tree[point].st, mid);
            tree[point].l=templ;
        }
        if(!tree[point].r){
            tempr=newNode(mid+1, tree[point].fin);
            tree[point].r=tempr;
        }
        in_LICHAO(tree[point].l, aa, bb);
        in_LICHAO(tree[point].r, aa, bb);
    }
    LL getfx(LL a){
        return findf(0, a);
    }
    void in(LL a, LL b){
        in_LICHAO(0, a, b);
    }
    DYNAMIC_Li_Chao(){
        newNode(-1000010LL, 1000010LL);
    }
}li;
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%lld", &h[i]);
    for(int i=1; i<=n; i++){
        scanf("%lld", &w[i]);
        sum[i]=sum[i-1]+w[i];
    }
    li.in(2*h[1], -h[1]*h[1]+sum[1]);
    for(int i=2; i<=n; i++){
        dp=-li.getfx(h[i])+h[i]*h[i]+sum[i-1];
        li.in(2*h[i], -dp-h[i]*h[i]+sum[i]);
    }
    printf("%lld", dp);
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
building.cpp:77:33: 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", &h[i]);
                            ~~~~~^~~~~~~~~~~~~~~
building.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &w[i]);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40