Submission #986548

#	Time	Username	Problem	Language	Result	Execution time	Memory
986548		idiotcomputer	Building Bridges (CEOI17_building)	C++11	60 / 100	65 ms	5712 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
 
//c + (hi - x)^2
// c + hi^2 + x^2 - 2hix
//lowest
struct line {
    ll m,c,x;
    bool t;
};
 
bool operator<(line a, line b){
    if (a.t || b.t) return a.x < b.x;
    if (a.m == b.m) return a.c > b.c;
    return a.m > b.m;
}
 
double isect(line a, line b){
    if (a.m == b.m) return INT_MIN;
    return ((double) (b.c-a.c) / (double) (a.m-b.m));
}
 
set<line> all;
 
void add(line a){
    auto it = all.lower_bound(a);
    if (it != all.end() && it != all.begin()){
        auto it2 = it;
        it2--;
        if (isect(*it2,a) >= isect(a,*it)) return;
    }
    //remove left 
    while (it != all.begin()){
        auto it2 = it;
        it2--;
        if (it2 == all.begin()) break;
        auto it3 = it2;
        it3--;
        if (isect(*it3,*it2) >= isect(*it2,a)) all.erase(it2);
        else break;
    }        
    //remove right
    while (it != all.end()){
        auto it2 = it;
        it2++;
        if (it2 == all.end()) break;
        if (isect(a,*it) >= isect(*it,*it2)){
            all.erase(it);
            it = it2;
        } else {
            break;
        }
    }
    if (it != all.begin()){
        line an = *prev(it);
        an.x = isect(*prev(it),a);
        all.erase(prev(it));
        all.insert(an);
        //it = all.lower_bound(a);
    }
    it = all.lower_bound(a);
    if (it != all.end()) a.x = isect(a,*it);
    all.insert(a);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    ll h[n];
    ll w[n];
    for (int i =0; i < n; i++) cin >> h[i];
    for (int i =0; i < n; i++) cin >> w[i];
    
    ll csum = 0;
    for (int i =0; i < n; i++) csum += w[i];
    //cout << csum << '\n';
    line temp;
    temp.m = -2*h[0];
    temp.c = h[0]*h[0]-w[0];
    temp.x = INT_MAX;
    temp.t = false;
    all.insert(temp);
 //   cout << temp.c - h[0]*h[0]<< "\n";
    for (int i = 1; i < n; i++){
        temp.t = true;
        temp.x = h[i];
        auto it = all.lower_bound(temp);
        temp.c = 2*h[i]*h[i] + ((*it).m * h[i] + (*it).c) - w[i];
        if (i == n-1) cout << csum + temp.c - h[i]*h[i] << '\n';
        temp.m = -2*h[i];
        temp.t = false;
        add(temp);
    }
    
    return 0;
}

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