Submission #469392

#	Time	Username	Problem	Language	Result	Execution time	Memory
469392		denkendoemeer	Building Bridges (CEOI17_building)	C++14	100 / 100	111 ms	9668 KiB

building

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct line
{
    int tip;
    double x;
    ll s,y;
};
bool operator < (const line &a,const line &b)
{
    if (a.tip+b.tip>0)
        return a.x<b.x;
    return a.s>b.s;
}
set<line>st;
typedef set<line>::iterator sti;
bool hasp(sti it)
{
    return it!=st.begin();
}
bool hasn(sti it)
{
    return it!=st.end() && next(it)!=st.end();
}
double inter(const sti a,const sti b)
{
    return (double)(a->y-b->y)/(b->s-a->s);
}
void calcx(sti it)
{
    if (hasp(it)){
        line aux=*it;
        aux.x=inter(prev(it),it);
        st.insert(st.erase(it),aux);
    }
}
bool rem(sti it)
{
    if (hasp(it) && hasn(it) && inter(it,next(it))<=inter(prev(it),next(it)))
        return 1;
    return 0;
}
void add(ll s,ll y)
{
    sti it=st.lower_bound((line){0,0,s,y});
    if (it!=st.end() && it->s==s){
        if (it->y<=y)
            return ;
        st.erase(it);
    }
    it=st.insert((line){0,0,s,y}).first;
    if (rem(it)){
        st.erase(it);
        return ;
    }
    while(hasp(it) && rem(prev(it)))
        st.erase(prev(it));
    while(hasn(it) && rem(next(it)))
        st.erase(next(it));
    if (hasn(it))
        calcx(next(it));
    calcx(it);
}
ll query(ll x)
{
    auto it=st.upper_bound((line){1,(double)x,0,0});
    it--;
    return it->s*x+it->y;
}
ll h[100005],w[100005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,i;
    ll cur,s=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&h[i]);
    for(i=1;i<=n;i++)
        scanf("%lld",&w[i]);
    s+=w[1];
    add(-2*h[1],h[1]*h[1]-w[1]);
    for(i=2;i<=n;i++){
        cur=query(h[i])+h[i]*h[i]-w[i];
        s+=w[i];
        add(-2*h[i],cur+h[i]*h[i]);
    }
    printf("%lld\n",s+cur);
return 0;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
building.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%lld",&h[i]);
      |         ~~~~~^~~~~~~~~~~~~~
building.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%lld",&w[i]);
      |         ~~~~~^~~~~~~~~~~~~~
building.cpp:90:11: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |     printf("%lld\n",s+cur);
      |     ~~~~~~^~~~~~~~~~~~~~~~

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