Submission #123218

#	Time	Username	Problem	Language	Result	Execution time	Memory
123218		davitmarg	Building Bridges (CEOI17_building)	C++17	100 / 100	130 ms	66540 KiB

building

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

struct line
{
    LL k,b;
    line(LL K=0,LL B=0)
    {
		k=K;
		b=B;
    }
};

LL F(line p,LL x)
{
    return p.k*x+p.b;
}

int n;
LL h[100005],pr[100005],dp[100005];
line t[4*1000006];

void build(int v,int l,int r)
{
    t[v]=line(-mod,-mod*mod);
    int m=(l+r)>>1;
    if(l==r)
		return;
    build(v*2,l,m);
    build(v*2+1,m+1,r);
}

void add(int v,LL l,LL r,line p)
{
    LL m=(l+r)>>1;
    bool L,M;
    L=(F(p,l)>F(t[v],l));
    M=(F(p,m)>F(t[v],m));
    if(M)
        swap(p,t[v]);
    if(l==r)
        return;
    else if(L!=M)
        add(v*2,l,m,p);
	else
        add(v*2+1,m+1,r,p);
}

LL get(int v,LL l,LL r,LL x)
{
    if(l==r)
		return F(t[v],x);
    LL m=(l+r)/2;
    if(x<=m)
        return max(F(t[v],x),get(v*2,l,m,x));
	else
        return max(F(t[v],x),get(v*2+1,m+1,r,x));
}

int main()
{
    cin>>n;
	for(int i=1;i<=n;i++)
        scanf("%lld",h+i);
	for(int i=1;i<=n;i++)
	{
        scanf("%lld",pr+i);
        pr[i]+=pr[i-1];
	}
    build(1,0,1000000);
    add(1,0,1000000,line(2*h[1],pr[1]-h[1]*h[1]));

	for(int i=2;i<=n;i++)
	{
		dp[i]=h[i]*h[i]+pr[i-1]-get(1,0,1000000,h[i]);
        add(1,0,1000000,line(2*h[i],pr[i]-dp[i]-h[i]*h[i]));
	}

    cout<<dp[n]<<endl;

	return 0;
}


/*

6
3 8 7 1 6 6
0 -1 9 1 2 0


*/

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",h+i);
         ~~~~~^~~~~~~~~~~~
building.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",pr+i);
         ~~~~~^~~~~~~~~~~~~

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