Submission #1114346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114346		proplayer	Building Bridges (CEOI17_building)	C++14	100 / 100	86 ms	12872 KiB

building

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
using lli = long long;
using ld = long double;
const int maxN = 1e5 + 5;
struct Tline
{
    bool type;
    ld x;
    lli a,b;
};
using setit = set<Tline>::iterator;
bool operator < (Tline l1,Tline l2)
{
    if (l1.type || l2.type) return l1.x < l2.x;
    return l1.a > l2.a;
}
struct Tcht
{
    set<Tline> cht;
    bool has_prev(setit it) {return it != cht.begin();}
    bool has_next(setit it) {return it != cht.end() && next(it) != cht.end();}
    ld cut(setit x,setit y) {return ld(x->b - y->b) / (y->a - x->a);}
    bool bad(setit it)
    {
        //if (has_next(it) && it->b >= next(it)->b) return true;
        return has_next(it) && has_prev(it) && cut(prev(it),next(it)) >= cut(it,next(it));
    }
    void calc_x(setit it)
    {
        if (has_prev(it))
        {
            Tline l = *it;
            l.x = cut(prev(it),it);
            cht.insert(cht.erase(it),l);
        }
    }
    void add(lli a,lli b)
    {
        setit it = cht.lower_bound({0,0,a,b});
        if (it != cht.end() && a == it->a)
        {
            if (it->b <= b) return;
            cht.erase(it);
        }
        it = cht.insert({0,0,a,b}).first;
        if (bad(it)) cht.erase(it);
        else
        {
            while (has_prev(it) && bad(prev(it))) cht.erase(prev(it));
            while (has_next(it) && bad(next(it))) cht.erase(next(it));
            if (has_next(it)) calc_x(next(it));
            calc_x(it);
        }
    }
    lli get(lli x)
    {
        Tline l = *prev(cht.upper_bound({1,ld(x),0,0}));
        return l.a * x + l.b;
    }
};
Tcht c;
lli h[maxN],w[maxN],sumw,n,f[maxN];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("XAYCAU.inp","r",stdin);
    //freopen("XAYCAU.out","w",stdout);
    cin >> n;sumw = 0;
    for (int i = 1;i <= n;++i) cin >> h[i];
    for (int i = 1;i <= n;++i)
    {
        cin >> w[i];
        sumw += w[i];
    }
    f[1] = -w[1];
    for (int i = 2;i <= n;++i)
    {
        c.add(-2 * h[i - 1],f[i - 1] + h[i - 1] * h[i - 1]);
        f[i] = c.get(h[i]) - w[i] + h[i] * h[i];
        //cout << c.get(h[i]) << " ";
    }
    cout << f[n] + sumw;
}

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