Submission #174675

#	Time	Username	Problem	Language	Result	Execution time	Memory
174675		rzbt	Building Bridges (CEOI17_building)	C++14	0 / 100	121 ms	40696 KiB

building

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

ll visina[MAXN],cena[MAXN];
ll n;
ll dp[MAXN];
ll prefix[MAXN];
pair<ll,ll> seg[4000006];

inline ll izr(pair<ll,ll> linija,ll tacka){
    return linija.F*tacka+linija.second;
}
ll manja(pair<ll,ll> l1,pair<ll,ll> l2,ll tacka){
    return l1.F*tacka+l1.S<l2.F*tacka+l2.S;

}


void dodaj(ll l,ll d,ll k,pair<ll,ll> linija){
    if(l==d){
        if(manja(linija,seg[k],l))seg[k]=linija;
        return;
    }

    ll mid=(l+d)/2;
    if(manja(seg[k],linija,l)==manja(seg[k],linija,d)){
        //printf(" SA ISTE STRANE   %lld %lld   %lld %lld    %lld %lld\n",l,d,linija.F,linija.S,seg[k].F,seg[k].S);
        if(manja(linija,seg[k],mid))seg[k]=linija;
        return;
    }
    /*if(izr(linija,mid)==izr(seg[k],mid)){
        printf(" NA SREDINI   %lld %lld   %lld %lld    %lld %lld\n",l,d,linija.F,linija.S,seg[k].F,seg[k].S);
        if(linija<seg[k])dodaj(mid+1,d,k+k+1,linija);
        else dodaj(l,mid,k+k,linija);
        return;
    }*/
    if(manja(seg[k],linija,l)==manja(seg[k],linija,mid)){
        if(manja(linija,seg[k],mid))swap(linija,seg[k]);
        //printf(" desno   %lld %lld   %lld %lld    %lld %lld\n",l,d,linija.F,linija.S,seg[k].F,seg[k].S);

        dodaj(mid+1,d,k+k+1,linija);


    }else{
        if(manja(linija,seg[k],mid))swap(linija,seg[k]);
        //printf("  levo   %lld %lld   %lld %lld    %lld %lld\n",l,d,linija.F,linija.S,seg[k].F,seg[k].S);
        dodaj(l,mid,k+k,linija);
    }


}

ll dobij(ll l,ll d,ll k,ll v){
    if(l==d)return izr(seg[k],v);
    ll mid=(l+d)/2;
    if(v<=mid)return min(izr(seg[k],v),dobij(l,mid,k+k,v));
    return min(izr(seg[k],v),dobij(mid+1,d,k+k+1,v));
}

void postavi(ll l,ll d,ll k){
    seg[k]=mp(0,1e14);
    if(l==d)return;
    ll mid=(l+d)/2;
    postavi(l,mid,k+k);
    postavi(mid+1,d,k+k+1);
}




int main()///dusan miskovic
{
    scanf("%lld", &n);
    for(ll i=1;i<=n;i++)scanf("%lld", visina+i);
    for(ll i=1;i<=n;i++)scanf("%lld", cena+i);

    for(ll i=1;i<=n;i++)prefix[i]=prefix[i-1]+cena[i];
    postavi(0,1e6+1,1);
    dodaj(0,1e6+1,1,mp(-2*visina[1],-cena[1]+visina[1]*visina[1]));

    for(ll i=2;i<=n;i++){

        dp[i]=dobij(0,1e6+1,1,visina[i])+prefix[i-1]+visina[i]*visina[i];
        dodaj(0,1e6+1,1,mp(-2*visina[i],visina[i]*visina[i]+dp[i]-prefix[i]));
        printf("   %lld  %lld  %lld\n",dp[i],prefix[i-1],visina[i]*visina[i]);
    }

    printf("%lld",dp[n]);

    return 0;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
building.cpp:83:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(ll i=1;i<=n;i++)scanf("%lld", visina+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~
building.cpp:84:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(ll i=1;i<=n;i++)scanf("%lld", cena+i);
                         ~~~~~^~~~~~~~~~~~~~~~

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