oj.uz

Submission #48425

# Submission time Handle Problem Language Result Execution time Memory
48425 2018-05-13T02:52:00 Z wzy Building Bridges (CEOI17_building) C++11
100 / 100
 149 ms 9164 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
long long w[100005] , h[100005];
long long n;
long long dp[100005];
struct line{
    int x , y;
    line(int x , int y){
        this->x = x , this->y = y;
    }
};

bool operator <(line a , line b){
    if(a.x == b.x) return a.y > b.y;
    else return a.x > b.x;
}
template <class type> 
class CHT{
    public : 
    bool cmp(type a , type b , type c){
        return ((double)((double) (c.y) - (a.y)) * ((double) (a.x) - (b.x))   <= ((double) ((double) (a.x) - (c.x)) * ((double) (b.y) - (a.y)) ) )  ; 
    }
    int sizex(){
        return cht.size();
    }
    void addLINE(type a){
            while(cht.size() >= 2 && cmp(cht[cht.size() - 2] , cht[cht.size() - 1] , a)){
                cht.pop_back();
            }
        cht.push_back(a);
    }
    int eval(type b , int a){
        int w = (b.x) * a + (b.y);
        return w;
    }
    void mergev(vector<type> nhcht){
        vector<type> newcht;
        for(int i = 0 ; i < nhcht.size() + cht.size() ; i++) newcht.pb(line(0,0));
        std::merge(nhcht.begin() , nhcht.end() , cht.begin() , cht.end() , newcht.begin() );
        cht.clear();
        for(int i = 0 ; i < newcht.size() ; i++) addLINE(newcht[i]);
    }
    int querymin(int x){
        if(cht.size() == 0) return (int) 1e18;
        int l = 0 , r = cht.size() - 1;
        r--;
        int ansj = -1;
        while(l<=r){
            int mid = (l+r)/2;
            if(eval(cht[mid] , x) >= eval(cht[mid + 1] , x)){
                l = mid + 1;
                ansj = mid;
            }
            else r = mid - 1;
        }
        int bestvalue = eval(cht.front() , x);
        if(ansj != -1) bestvalue = min(bestvalue , eval(cht[ansj] , x));
        ansj ++;
        if(ansj < cht.size()) bestvalue = min(bestvalue , eval(cht[ansj] , x));

        return bestvalue;
    }
    vector<type> vectorT(){
        return cht;
    }
    void clearv(){
        cht.clear();
    }
    vector<type> cht;
}; 

CHT <line> chts[33];

void addline(line a){
    vector<line> v;
    v.push_back(a);
    chts[0].mergev(v);
    for(int i = 0 ; i < 32 ; i++){
        int z = (1LL<<i);
        if(chts[i].sizex() > z){
            chts[i+1].mergev(chts[i].vectorT());
            chts[i].clearv();
        }
    }
    return ;
}


long long query(int x){

    long long bestvalue = (long long) 1e18;
    for(int i = 0 ; i < 32 ; i++){
        bestvalue  = min(bestvalue , chts[i].querymin(x));
    }
    return bestvalue;
}


int32_t main(){
    scanf("%lld" , &n);
    dp[0] = 0;
    for(int i = 1 ; i <=n ;i ++){
        scanf("%lld" , &h[i]);
    }
    w[0] = 0;
    for(int i = 1 ; i <=n ;i ++){
        scanf("%lld" , &w[i]);
        w[i] += w[i-1];
    }
    dp[1] = 0;
    addline(line(-2*h[1] , h[1]*h[1]  - w[1] ));
    for(int i = 2 ; i <= n ;i ++){
        dp[i] = query(h[i]) + h[i]*h[i] + w[i-1];
        addline(line(-2*h[i] , h[i]*h[i] - w[i] + dp[i]));
    }
    printf("%lld\n" , dp[n]);
}

Compilation message

building.cpp: In instantiation of 'void CHT<type>::mergev(std::vector<_Tp>) [with type = line]':
building.cpp:79:21:   required from here
building.cpp:40:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < nhcht.size() + cht.size() ; i++) newcht.pb(line(0,0));
building.cpp:43:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < newcht.size() ; i++) addLINE(newcht[i]);
building.cpp: In instantiation of 'long long int CHT<type>::querymin(long long int) [with type = line]':
building.cpp:95:56:   required from here
building.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ansj < cht.size()) bestvalue = min(bestvalue , eval(cht[ansj] , x));
building.cpp: In function 'int32_t main()':
building.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld" , &n);
     ~~~~~^~~~~~~~~~~~~
building.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld" , &h[i]);
         ~~~~~^~~~~~~~~~~~~~~~
building.cpp:109: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 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 3 ms 408 KB Output is correct
5 Correct 3 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 2948 KB Output is correct
2 Correct 149 ms 2948 KB Output is correct
3 Correct 146 ms 2956 KB Output is correct
4 Correct 131 ms 2956 KB Output is correct
5 Correct 118 ms 5820 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 3 ms 408 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 145 ms 2948 KB Output is correct
7 Correct 149 ms 2948 KB Output is correct
8 Correct 146 ms 2956 KB Output is correct
9 Correct 131 ms 2956 KB Output is correct
10 Correct 118 ms 5820 KB Output is correct
11 Correct 141 ms 5820 KB Output is correct
12 Correct 149 ms 5820 KB Output is correct
13 Correct 96 ms 5820 KB Output is correct
14 Correct 146 ms 5820 KB Output is correct
15 Correct 140 ms 9164 KB Output is correct
16 Correct 133 ms 9164 KB Output is correct
17 Correct 63 ms 9164 KB Output is correct
18 Correct 79 ms 9164 KB Output is correct