oj.uz

Submission #46339

# Submission time Handle Problem Language Result Execution time Memory
46339 2018-04-19T13:25:23 Z RezwanArefin01 Building Bridges (CEOI17_building) C++17
0 / 100
 106 ms 6080 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int maxn = 1e5 + 10; 
const ll isQuery = -(1ll << 62);

struct line {
	ll m, b;
	mutable function<const line*()> succ; 
	bool operator < (const line &l) const {
		if(l.b != isQuery) return m < l.m; 
		const line* s = succ(); 
		if(!s) return 0;
		return b - s -> b < (s -> m - m) * l.m;
	}	
};
struct cht : public multiset<line> {
	bool bad(iterator y) {
		auto z = next(y);
		if(y == begin()) {
			if(z == end()) return 0; 
			return y -> m == z -> m && y -> b <= z -> b;
		}
		auto x = prev(y);
		if(z == end()) return y -> m == x -> m && y -> b <= x -> b;
		return 1.0 * (z -> b - x -> b) * (x -> m - y -> m) <= 1.0 * (y -> b - x -> b) * (x -> m - z -> m);
	}
	void add(ll m, ll b) { 
		auto y = insert({-m, -b}); 
		y -> succ = [=]{ return next(y) == end() ? 0 : &*next(y); }; 
		if(bad(y)) return (void) erase(y); 
		while(next(y) != end() && bad(next(y))) erase(next(y)); 
		while(y != begin() && bad(prev(y))) erase(prev(y));
	}
	ll eval(ll x) {
		auto it = *lower_bound({x, isQuery}); 
		return -(it.m * x + it.b);
	}
} ds;
int n, h[maxn], w[maxn]; 
ll dp[maxn], sum;

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n; scanf("%d", &n); 
	for(int i = 1; i <= n; i++) 
		scanf("%d", &h[i]);
	for(int i = 1; i <= n; i++) 
		scanf("%d", &w[i]), sum += w[i]; 

	dp[1] = -w[1]; 
	ds.add(-2ll * h[1], dp[1] + (ll) h[1] * h[1]);
	for(int i = 1; i <= n; i++) {
		dp[i] = ds.eval(h[i]) + (ll) h[i] * h[i] - w[i];
		ds.add(-2ll * h[i], dp[i] + (ll) h[i] * h[i]);
	}

	printf("%lld\n", dp[n] + sum);
}

Compilation message

building.cpp: In function 'int main(int, const char**)':
building.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n); 
         ~~~~~^~~~~~~~~~
building.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &h[i]);
   ~~~~~^~~~~~~~~~~~~
building.cpp:54:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i]), sum += w[i]; 
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 3056 KB Output is correct
2 Correct 89 ms 4220 KB Output is correct
3 Correct 106 ms 5240 KB Output is correct
4 Incorrect 83 ms 6080 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -