oj.uz

Submission #168221

# Submission time Handle Problem Language Result Execution time Memory
168221 2019-12-12T03:04:29 Z mhy908 Building Bridges (CEOI17_building) C++14
100 / 100
 99 ms 14032 KB 
#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

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

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 4532 KB Output is correct
2 Correct 99 ms 4532 KB Output is correct
3 Correct 99 ms 4520 KB Output is correct
4 Correct 92 ms 4200 KB Output is correct
5 Correct 92 ms 8904 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 99 ms 4532 KB Output is correct
7 Correct 99 ms 4532 KB Output is correct
8 Correct 99 ms 4520 KB Output is correct
9 Correct 92 ms 4200 KB Output is correct
10 Correct 92 ms 8904 KB Output is correct
11 Correct 91 ms 4328 KB Output is correct
12 Correct 98 ms 4532 KB Output is correct
13 Correct 70 ms 3832 KB Output is correct
14 Correct 99 ms 4660 KB Output is correct
15 Correct 94 ms 14032 KB Output is correct
16 Correct 88 ms 9160 KB Output is correct
17 Correct 28 ms 3704 KB Output is correct
18 Correct 26 ms 3832 KB Output is correct