oj.uz

Submission #203535

# Submission time Handle Problem Language Result Execution time Memory
203535 2020-02-21T06:52:26 Z wendy_virgo Building Bridges (CEOI17_building) C++14
100 / 100
 91 ms 35964 KB 
#include <bits/stdc++.h>

using namespace std;

#define taskname "CEOI17_building"
#define forinc(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordec(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define foreach(i, x) for (auto &i : x)
#define ms(x, n) memset(x, n, sizeof(x))
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define fi first
#define se second
#define pb push_back
#define pf push_front

template<typename TH>
void _dbg(const char* sdbg, TH h)
{
	cerr << sdbg << " = " << h << "\n";
}

template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
	while (*sdbg != ',') cerr << *sdbg++;
	cerr << " = " << h << ",";
	_dbg(sdbg + 1, t...);
}

#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";

const int N=1e5+5,H=1e6+6;
const int64_t LINF=1e18;

int n,h[N],w[N];
int64_t f[N];

struct Line
{
    int64_t a,b;
};

Line st[4*H];

int64_t Get(Line d,int64_t x)
{
    return d.a*x+d.b;
}

void Build(int id,int l,int r)
{
    if(l==r)
    {
        st[id]={0,LINF};
        return;
    }
    Build(id*2,l,(l+r)/2);
    Build(id*2+1,(l+r)/2+1,r);
    st[id]={0,LINF};
}

void Update(int id,int l,int r,int i,int j,Line val)
{
    if(r<i||l>j)
    {
        return;
    }
    int mid=(l+r)/2;
    if(i<=l&&r<=j)
    {
        if(Get(st[id],l)<=Get(val,l)&&Get(st[id],r)<=Get(val,r))
        {
            return;
        }
        if(Get(st[id],l)>=Get(val,l)&&Get(st[id],r)>=Get(val,r))
        {
            st[id]=val;
            return;
        }
        if(Get(st[id],l)<=Get(val,l)&&Get(st[id],mid)<=Get(val,mid))
        {
            Update(id*2+1,mid+1,r,i,j,val);
            return;
        }
        if(Get(st[id],l)>=Get(val,l)&&Get(st[id],mid)>=Get(val,mid))
        {
            Update(id*2+1,mid+1,r,i,j,st[id]);
            st[id]=val;
            return;
        }
        if(Get(st[id],mid+1)<=Get(val,mid+1)&&Get(st[id],r)<=Get(val,r))
        {
            Update(id*2,l,mid,i,j,val);
            return;
        }
        if(Get(st[id],mid+1)>=Get(val,mid+1)&&Get(st[id],r)>=Get(val,r))
        {
            Update(id*2,l,mid,i,j,st[id]);
            st[id]=val;
            return;
        }
        return;
    }
    Update(id*2,l,mid,i,j,val);
    Update(id*2+1,mid+1,r,i,j,val);
}

int64_t Query(int id,int l,int r,int64_t x)
{
    if(r<x||l>x)
    {
        return LINF;
    }
    int64_t res=Get(st[id],x);
    if(l==r)
    {
        return res;
    }
    res=min(res,Query(id*2,l,(l+r)/2,x));
    res=min(res,Query(id*2+1,(l+r)/2+1,r,x));
    return res;
}

void Sub1()
{
    int64_t sumW=0;
    forinc(i,1,n)
    {
        sumW+=w[i];
    }
    f[1]=-w[1];
    forinc(i,2,n)
    {
        f[i]=LINF;
        forinc(j,1,i-1)
        {
            f[i]=min(f[i],f[j]+(int64_t)(h[i]-h[j])*(h[i]-h[j])-w[i]);
        }
    }
    cout<<f[n]+sumW;
}

void Sub3()
{
    Build(1,0,H-1);
    int64_t sumW=0;
    forinc(i,1,n)
    {
        sumW+=w[i];
    }
    //f[j]+h[i]^2-2*h[i]*h[j]+h[j]^2-w[i]
    //f[j]-2*h[j]+h[j]^2
    f[1]=-w[1];
    Update(1,0,H-1,0,H-1,{(int64_t)-2*h[1],f[1]+(int64_t)h[1]*h[1]});
    forinc(i,2,n)
    {
        f[i]=LINF;
//        forinc(j,1,i-1)
//        {
//            f[i]=min(f[i],f[j]+(int64_t)(h[i]-h[j])*(h[i]-h[j])-w[i]);
//        }
        f[i]=Query(1,0,H-1,h[i])+(int64_t)h[i]*h[i]-w[i];
        Update(1,0,H-1,0,H-1,{(int64_t)-2*h[i],f[i]+(int64_t)h[i]*h[i]});
    }
    cout<<f[n]+sumW;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifndef ONLINE_JUDGE
//	freopen(taskname".INP","r",stdin);
	#endif // ONLINE_JUDGE
	cin>>n;
	forinc(i,1,n)
	{
	    cin>>h[i];
	}
	forinc(i,1,n)
	{
	    cin>>w[i];
	}
	Sub3();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33144 KB Output is correct
2 Correct 26 ms 33144 KB Output is correct
3 Correct 26 ms 33144 KB Output is correct
4 Correct 27 ms 33144 KB Output is correct
5 Correct 27 ms 33144 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 35704 KB Output is correct
2 Correct 85 ms 35832 KB Output is correct
3 Correct 82 ms 35832 KB Output is correct
4 Correct 80 ms 35704 KB Output is correct
5 Correct 76 ms 35704 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33144 KB Output is correct
2 Correct 26 ms 33144 KB Output is correct
3 Correct 26 ms 33144 KB Output is correct
4 Correct 27 ms 33144 KB Output is correct
5 Correct 27 ms 33144 KB Output is correct
6 Correct 87 ms 35704 KB Output is correct
7 Correct 85 ms 35832 KB Output is correct
8 Correct 82 ms 35832 KB Output is correct
9 Correct 80 ms 35704 KB Output is correct
10 Correct 76 ms 35704 KB Output is correct
11 Correct 91 ms 35960 KB Output is correct
12 Correct 85 ms 35704 KB Output is correct
13 Correct 78 ms 35832 KB Output is correct
14 Correct 87 ms 35960 KB Output is correct
15 Correct 80 ms 35576 KB Output is correct
16 Correct 76 ms 35704 KB Output is correct
17 Correct 64 ms 35964 KB Output is correct
18 Correct 66 ms 35960 KB Output is correct