Submission #129502

#	Time	Username	Problem	Language	Result	Execution time	Memory
129502		semiauto	Building Bridges (CEOI17_building)	C++14	0 / 100	150 ms	35848 KiB

building

#include <bits/stdc++.h>
using namespace std;
const long long N=1024*1024,inf=N*N*N;
long long n,i,sum;
long long s[N],h[N];
pair <long long,long long> tree[2*N];
long long val(pair <long long,long long> line,long long x) {
    return x*line.first+line.second;
}
long long solve(long long x) {
    long long pos=x+N,ret=inf;
    while (pos) {
        ret=min(ret,val(tree[pos],x));
        pos/=2;
    }
    return ret;
}
void add_line(pair <long long,long long> line,long long p,long long l,long long r) {
    long long m=(l+r)/2;
    bool lef=val(line,l)<val(tree[p],l);
    bool mid=val(line,m)<val(tree[p],m);
    if (mid)
        swap(tree[p],line);
    if (p<N) {
        if (lef!=mid)
            add_line(line,2*p,l,m);
        else
            add_line(line,2*p+1,m,r);
    }
    return;
}
int main() {
	cin>>n;
	for (i=1;i<=n;i++)
		cin>>h[i];
	for (i=1;i<=n;i++) {
        cin>>s[i];
        sum+=s[i];
	}
	for (i=1;i<(2*N);i++)
        tree[i]={-2*h[1],h[1]*h[1]-s[1]};
	for (i=2;i<n;i++)
        add_line({-2*h[i],2*h[i]*h[i]-s[i]+solve(h[i])},1,N,2*N);
	cout<<solve(h[n])+sum+h[n]*h[n]-s[n]<<endl;
	return 0;
}

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