답안 #48424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48424 2018-05-13T02:48:18 Z wzy Building Bridges (CEOI17_building) C++11
컴파일 오류
0 ms 0 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 merge(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;

void addline(line a){
    vector<line> v;
    v.push_back(a);
    chts[0].merge(v);
    for(int i = 0 ; i < 32 ; i++){
        int z = (1LL<<i);
        if(chts[i].sizex() > z){
            chts[i+1].merge(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 function 'void addline(line)':
building.cpp:79:9: error: no match for 'operator[]' (operand types are 'CHT<line>' and 'int')
     chts[0].merge(v);
         ^
building.cpp:82:16: error: no match for 'operator[]' (operand types are 'CHT<line>' and 'long long int')
         if(chts[i].sizex() > z){
                ^
building.cpp:83:17: error: no match for 'operator[]' (operand types are 'CHT<line>' and 'long long int')
             chts[i+1].merge(chts[i].vectorT());
                 ^
building.cpp:83:33: error: no match for 'operator[]' (operand types are 'CHT<line>' and 'long long int')
             chts[i+1].merge(chts[i].vectorT());
                                 ^
building.cpp:84:17: error: no match for 'operator[]' (operand types are 'CHT<line>' and 'long long int')
             chts[i].clearv();
                 ^
building.cpp: In function 'long long int query(long long int)':
building.cpp:95:42: error: no match for 'operator[]' (operand types are 'CHT<line>' and 'long long int')
         bestvalue  = min(bestvalue , chts[i].querymin(x));
                                          ^
building.cpp: In function 'int32_t main()':
building.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
  ~~~~~^~~~~~~~~~~~~
building.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &h[i]);
   ~~~~~^~~~~~~~~~~~~~~~
building.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &w[i]);
   ~~~~~^~~~~~~~~~~~~~~~