oj.uz

Submission #721427

# Submission time Handle Problem Language Result Execution time Memory
721427 2023-04-10T21:54:46 Z Dan4Life Building Bridges (CEOI17_building) C++17
100 / 100
 75 ms 35132 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxN = (int)1e5+10;
const int mxC = (int)1e6+10;
const int LINF = (int)1e12+10;
int n, m, x, h[mxN], w[mxN], dp[mxN];

struct Line{
	int m, c;
	Line(){ m=c=LINF; }
	Line(int _m, int _c){ m = _m, c = _c;}
	int operator()(int x){ return m*x+c; }
} seg[2*mxC+10];

void addLine(Line a, int p=0, int l=1, int r=mxC){
	if(l==r){
		if(seg[p](l)>a(l)) seg[p]=a;
		return;
	}
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	if(a.m > seg[p].m) swap(a,seg[p]);
	if(a(mid) < seg[p](mid))
		swap(a,seg[p]), addLine(a,p+1,l,mid);
	else addLine(a,rp,mid+1,r);
}

int query(int x, int p=0, int l=1, int r=mxC){
	if(l==r) return seg[p](x);
	int mid = (l+r)>>1; int rp = p+2*(mid-l+1);
	if(x<=mid) return min(query(x,p+1,l,mid),seg[p](x));
	return min(query(x,rp,mid+1,r),seg[p](x));
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n; 
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) cin >> w[i];
	dp[1] = -w[1];
	for(int i = 1; i <= n; i++){
		if(i>1)dp[i] = query(h[i])+h[i]*h[i]-w[i];
		addLine({-2*h[i],dp[i]+h[i]*h[i]});
	}
	cout << accumulate(w+1,w+n+1,0ll)+dp[n];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 12 ms 31572 KB Output is correct
3 Correct 12 ms 31576 KB Output is correct
4 Correct 14 ms 31660 KB Output is correct
5 Correct 14 ms 31572 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 33916 KB Output is correct
2 Correct 49 ms 33908 KB Output is correct
3 Correct 48 ms 33904 KB Output is correct
4 Correct 47 ms 33868 KB Output is correct
5 Correct 42 ms 33912 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 12 ms 31572 KB Output is correct
3 Correct 12 ms 31576 KB Output is correct
4 Correct 14 ms 31660 KB Output is correct
5 Correct 14 ms 31572 KB Output is correct
6 Correct 64 ms 33916 KB Output is correct
7 Correct 49 ms 33908 KB Output is correct
8 Correct 48 ms 33904 KB Output is correct
9 Correct 47 ms 33868 KB Output is correct
10 Correct 42 ms 33912 KB Output is correct
11 Correct 75 ms 35132 KB Output is correct
12 Correct 69 ms 34928 KB Output is correct
13 Correct 51 ms 34980 KB Output is correct
14 Correct 55 ms 35048 KB Output is correct
15 Correct 43 ms 34764 KB Output is correct
16 Correct 44 ms 34800 KB Output is correct
17 Correct 36 ms 34944 KB Output is correct
18 Correct 35 ms 35008 KB Output is correct