oj.uz

Submission #964220

# Submission time Handle Problem Language Result Execution time Memory
964220 2024-04-16T12:35:25 Z pcc Building Bridges (CEOI17_building) C++17
100 / 100
 56 ms 73348 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const ll inf = 1e18;
const ll mxn = 1e6+10;

struct line{
	ll m,b;
	line(){
		m = 0;
		b = inf;
	}
	line(ll mm,ll bb):m(mm),b(bb){}
	ll operator()(ll x){
		return m*x+b;
	}
};



struct SEG{
	line seg[mxn*4];
	SEG(){}
	void addline(int now,int l,int r,line k){
		if(l == r){
			if(seg[now](l)>k(l))swap(seg[now],k);
			return;
		}
		int mid = (l+r)>>1;
		if(seg[now](mid)>k(mid))swap(seg[now],k);
		if(seg[now].m<k.m)addline(now*2+1,l,mid,k);
		else addline(now*2+2,mid+1,r,k);
		return;
	}
	ll getval(int now,int l,int r,int p){
		if(l == r)return seg[now](p);
		int mid = (l+r)>>1;
		if(mid>=p)return min(seg[now](p),getval(now*2+1,l,mid,p));
		else return min(seg[now](p),getval(now*2+2,mid+1,r,p));
	}
};

SEG seg;
ll H[mxn],pref[mxn];
ll N;
ll dp[mxn];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++)cin>>H[i];
	for(int i = 1;i<=N;i++)cin>>pref[i],pref[i] += pref[i-1];
	seg.addline(0,0,mxn-1,line(-H[1]*2,dp[1]+H[1]*H[1]-pref[1]));
	for(int i = 2;i<=N;i++){
		dp[i] = seg.getval(0,0,mxn-1,H[i])+pref[i-1]+H[i]*H[i];
		seg.addline(0,0,mxn-1,line(-H[i]*2,dp[i]+H[i]*H[i]-pref[i]));
	}
	cout<<dp[N];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 67852 KB Output is correct
2 Correct 12 ms 67932 KB Output is correct
3 Correct 11 ms 67852 KB Output is correct
4 Correct 12 ms 67824 KB Output is correct
5 Correct 13 ms 67932 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 73044 KB Output is correct
2 Correct 42 ms 72996 KB Output is correct
3 Correct 51 ms 73140 KB Output is correct
4 Correct 47 ms 73032 KB Output is correct
5 Correct 43 ms 73108 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 67852 KB Output is correct
2 Correct 12 ms 67932 KB Output is correct
3 Correct 11 ms 67852 KB Output is correct
4 Correct 12 ms 67824 KB Output is correct
5 Correct 13 ms 67932 KB Output is correct
6 Correct 44 ms 73044 KB Output is correct
7 Correct 42 ms 72996 KB Output is correct
8 Correct 51 ms 73140 KB Output is correct
9 Correct 47 ms 73032 KB Output is correct
10 Correct 43 ms 73108 KB Output is correct
11 Correct 56 ms 73148 KB Output is correct
12 Correct 53 ms 73180 KB Output is correct
13 Correct 41 ms 73204 KB Output is correct
14 Correct 52 ms 73348 KB Output is correct
15 Correct 36 ms 73048 KB Output is correct
16 Correct 47 ms 73044 KB Output is correct
17 Correct 32 ms 73048 KB Output is correct
18 Correct 36 ms 73136 KB Output is correct