제출 #927933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927933		TAhmed33	Building Bridges (CEOI17_building)	C++98	100 / 100	79 ms	35260 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAX = 1e6 + 25;
struct line {
  int m = 1e10, b = 1e12;
  int operator() (int x) { return m * x + b; }
};
vector <line> tree(MAX * 2);
void insert (int l, int r, line a, int node) {
  if (l == r) {
    if (tree[node](l) > a(l)) {
      tree[node] = a;
    }
    return;
  }
  if (tree[node].m > a.m) swap(tree[node], a);
  if (tree[node](mid) > a(mid)) {
    swap(tree[node], a);
    insert(mid + 1, r, a, tr);
  } else {
    insert(l, mid, a, tl);
  }
}
int get (int l, int r, int a, int node) {
  if (l == r) {
    return tree[node](a);
  }
  if (a <= mid) return min(tree[node](a), get(l, mid, a, tl));
  else return min(tree[node](a), get(mid + 1, r, a, tr));
}
int n;
const int MAXN = 1e5 + 25;
int a[MAXN], b[MAXN];
int dp[MAXN];
signed main () {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		b[i] += b[i - 1];
	}
	insert(0, MAX, {-2 * a[1], dp[1] + a[1] * a[1] - b[1]}, 1);
	for (int i = 2; i <= n; i++) {
		int val = get(0, MAX, a[i], 1);
		dp[i] += val + a[i] * a[i] + b[i - 1];
		insert(0, MAX, {-2 * a[i], dp[i] + a[i] * a[i] - b[i]}, 1);
	}
	cout << dp[n] << '\n';
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40