oj.uz

Submission #129519

# Submission time Handle Problem Language Result Execution time Memory
129519 2019-07-12T11:51:53 Z semiauto Building Bridges (CEOI17_building) C++14
100 / 100
 172 ms 35944 KB 
#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-N)<val(tree[p],l-N);
    bool mid=val(line,m-N)<val(tree[p],m-N);
    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33144 KB Output is correct
2 Correct 28 ms 33144 KB Output is correct
3 Correct 29 ms 33144 KB Output is correct
4 Correct 30 ms 33144 KB Output is correct
5 Correct 30 ms 33144 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 34808 KB Output is correct
2 Correct 141 ms 34780 KB Output is correct
3 Correct 142 ms 35708 KB Output is correct
4 Correct 133 ms 35704 KB Output is correct
5 Correct 134 ms 35704 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33144 KB Output is correct
2 Correct 28 ms 33144 KB Output is correct
3 Correct 29 ms 33144 KB Output is correct
4 Correct 30 ms 33144 KB Output is correct
5 Correct 30 ms 33144 KB Output is correct
6 Correct 141 ms 34808 KB Output is correct
7 Correct 141 ms 34780 KB Output is correct
8 Correct 142 ms 35708 KB Output is correct
9 Correct 133 ms 35704 KB Output is correct
10 Correct 134 ms 35704 KB Output is correct
11 Correct 172 ms 35944 KB Output is correct
12 Correct 148 ms 35832 KB Output is correct
13 Correct 145 ms 35832 KB Output is correct
14 Correct 159 ms 35848 KB Output is correct
15 Correct 130 ms 35588 KB Output is correct
16 Correct 133 ms 35704 KB Output is correct
17 Correct 138 ms 35848 KB Output is correct
18 Correct 138 ms 35824 KB Output is correct