oj.uz

Submission #174676

# Submission time Handle Problem Language Result Execution time Memory
174676 2020-01-06T16:16:14 Z rzbt Building Bridges (CEOI17_building) C++14
100 / 100
 103 ms 37496 KB 
#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

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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 33144 KB Output is correct
2 Correct 35 ms 33144 KB Output is correct
3 Correct 34 ms 33144 KB Output is correct
4 Correct 35 ms 33272 KB Output is correct
5 Correct 38 ms 33244 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 36304 KB Output is correct
2 Correct 100 ms 37412 KB Output is correct
3 Correct 91 ms 37348 KB Output is correct
4 Correct 90 ms 37240 KB Output is correct
5 Correct 83 ms 37240 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 33144 KB Output is correct
2 Correct 35 ms 33144 KB Output is correct
3 Correct 34 ms 33144 KB Output is correct
4 Correct 35 ms 33272 KB Output is correct
5 Correct 38 ms 33244 KB Output is correct
6 Correct 88 ms 36304 KB Output is correct
7 Correct 100 ms 37412 KB Output is correct
8 Correct 91 ms 37348 KB Output is correct
9 Correct 90 ms 37240 KB Output is correct
10 Correct 83 ms 37240 KB Output is correct
11 Correct 103 ms 37460 KB Output is correct
12 Correct 101 ms 37256 KB Output is correct
13 Correct 85 ms 37368 KB Output is correct
14 Correct 101 ms 37496 KB Output is correct
15 Correct 85 ms 37240 KB Output is correct
16 Correct 82 ms 37212 KB Output is correct
17 Correct 66 ms 37368 KB Output is correct
18 Correct 66 ms 37468 KB Output is correct