oj.uz

답안 #99029

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
99029 2019-02-28T06:46:38 Z arman_ferdous Building Bridges (CEOI17_building) C++17
0 / 100
 113 ms 67152 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e5+100;
const int MAX = 1e6+100;
const ll inf = 1e18;

struct LiChao{
	struct pt{ ll m, c; };
	ll eval(pt p, ll x) { return p.m * x + p.c; }

	pt t[MAX<<2];
	LiChao() { for(int i = 0; i < (MAX<<2); i++) t[i] = {0,inf}; }
	
	void insert(int node, int L, int R, pt p) {
		if(L == R) {
			if(eval(p,L) < eval(t[node],L)) t[node] = p;
			return;
		} int mid = (L+R)>>1, lc = node<<1, rc = lc|1;

		bool one = eval(p,L) < eval(t[node],L);
		bool two = eval(p,mid) < eval(t[node],mid);

		if(one && two) {
			t[node] = p;
			insert(rc, mid+1, R, p);
		} else if(one) insert(lc, L, mid, p);
		else if(two) {
			t[node] = p;
			insert(lc, L, mid, p);
		} else insert(rc, mid+1, R, p);
	}
	ll get(int node, int L, int R, ll x) {
		if(L == R) return eval(t[node], x);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		if(x <= mid) return min(eval(t[node], x), get(lc, L, mid, x));
		return min(eval(t[node], x), get(rc, mid+1, R, x));
	}
}ds;

int n;
ll h[N], w[N], S[N], dp[N];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &h[i]);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &w[i]);
		S[i] = S[i-1] + w[i];
	}
	dp[1] = 0;
	ds.insert(1, 0, MAX-1, {-2ll*h[1], h[1]*h[1] - S[1]});
	for(int i = 2; i <= n; i++) {
		ll got = ds.get(1, 0, MAX-1, h[i]);
		dp[i] = got + h[i] * h[i] + S[i-1];
		ds.insert(1, 0, MAX-1, {-2ll*h[i], dp[i] - S[i] + h[i] * h[i]});
	}
	printf("%lld\n", dp[n]);
	return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &h[i]);
   ~~~~~^~~~~~~~~~~~~~~
building.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &w[i]);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 62968 KB Output is correct
2 Incorrect 49 ms 62968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 113 ms 67152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 62968 KB Output is correct
2 Incorrect 49 ms 62968 KB Output isn't correct
3 Halted 0 ms 0 KB -