oj.uz

Submission #252011

# Submission time Handle Problem Language Result Execution time Memory
252011 2020-07-23T15:34:51 Z lyc Building Bridges (CEOI17_building) C++14
60 / 100
 167 ms 5620 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
#define SQ(x) ((ll)(x)*(x))
using ll=long long;
using ld=long double;
using ii=pair<int,int>;

const int mxN = 1e5+5;

int N, H[mxN], W[mxN];
ll pW[mxN], dp[mxN];

struct Line {
	ll m, c;
	ll eval(ll x) { return m*x + c; }
};

struct Hull {
	Line dq[mxN];
	int s, e;
	
	inline void reset() { s = e = 0; }
	
	Hull() { reset(); }
	
	inline ld intersect(Line a, Line b) {
		return (ld)(a.c - b.c) / (b.m - a.m);
	}
	
	void add(ll m, ll c) {
		Line l = {m,c};
		while (e-s > 1 && dq[e-1].m > m && intersect(l,dq[e-1]) <= intersect(dq[e-1],dq[e-2])) --e;
		if (e > s && dq[e-1].m == m) {
			if (dq[e-1].c > c) --e;
			else return;
		}
		dq[e++] = l;
	}
	
	ll query(ll x) {
		while (e-s > 1 && dq[s].eval(x) >= dq[s+1].eval(x)) ++s;
		return dq[s].eval(x);
	}
} ch;

void cdq(int l, int r) {
	if (l == r) return;
	int m = (l+r)/2;
	cdq(l,m);
	
	ch.reset();
	vector<ii> slopes, queries;
	FOR(i,l,m){
		slopes.emplace_back(-2*H[i],i);
	}
	FOR(i,m+1,r){
		queries.emplace_back(H[i],i);
	}
	sort(ALL(slopes),greater<ii>());
	sort(ALL(queries));
	
	// (H[i]-H[j])^2 + pW[i-1]-pW[j] + dp[j];
	for (auto& s : slopes) {
		int i = s.second;
		ch.add(-2*H[i], SQ(H[i]) - pW[i] + dp[i]);
	}
	for (auto& q : queries) {
		int i = q.second;
		dp[i] = min(dp[i], ch.query(H[i]) + SQ(H[i]) + pW[i-1]);
	}
	
	cdq(m+1,r);
}

int main() {
	//freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    FOR(i,1,N){ cin >> H[i]; }
    FOR(i,1,N){ cin >> W[i]; pW[i] = pW[i-1] + W[i]; }
    
    dp[1] = 0;
    FOR(i,2,N) dp[i] = 1e18;
    cdq(1,N);
	cout << dp[N] << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4476 KB Output is correct
2 Correct 145 ms 5496 KB Output is correct
3 Correct 151 ms 5380 KB Output is correct
4 Correct 151 ms 5360 KB Output is correct
5 Correct 90 ms 5620 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 167 ms 4476 KB Output is correct
7 Correct 145 ms 5496 KB Output is correct
8 Correct 151 ms 5380 KB Output is correct
9 Correct 151 ms 5360 KB Output is correct
10 Correct 90 ms 5620 KB Output is correct
11 Correct 147 ms 5504 KB Output is correct
12 Correct 144 ms 5376 KB Output is correct
13 Incorrect 159 ms 5500 KB Output isn't correct
14 Halted 0 ms 0 KB -