Submission #115215

#	Time	Username	Problem	Language	Result	Execution time	Memory
115215		IOrtroiii	Building Bridges (CEOI17_building)	C++14	100 / 100	127 ms	64632 KiB

building

/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll inf = 1e18;
const int N = 100100;
const int H = 1000100;

struct Line {
   int a; ll b;
   Line(int a = 0, ll b = inf) : a(a), b(b) {}
   ll f(int x) { return (ll) a * x + b; }
};

Line t[H << 2];

void add(int v, int l, int r, Line val) {
   if (t[v].f(l) >= val.f(l) && t[v].f(r) >= val.f(r)) {
      t[v] = val;  return;
   }
   if (t[v].f(l) <= val.f(l) && t[v].f(r) <= val.f(r)) {
      return;
   }
   int md = (l + r) >> 1;
   add(v << 1, l, md, val);
   add(v << 1 | 1, md + 1, r, val);
}

ll get(int v, int l, int r, int x) {
   if (l == r) { return t[v].f(x); }
   ll ans = t[v].f(x);
   int md = (l + r) >> 1;
   if (x <= md) ans = min(ans, get(v << 1, l, md, x));
   else ans = min(ans, get(v << 1 | 1, md + 1, r, x));
   return ans;
}

int n;
int h[N], w[N];
ll f[N];

int main() {
   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);
   }
   for (int i = 1; i <= n; ++i) {
      if (i == 1) {
         f[i] = -w[i];
      } else {
         f[i] = get(1, 0, H - 1, h[i]) + (ll) h[i] * h[i] - w[i];
      }
      add(1, 0, H - 1, Line(-2 * h[i], (ll) h[i] * h[i] + f[i]));
   }
   ll ans = f[n];
   for (int i = 1; i <= n; ++i) {
      ans += w[i];
   }
   printf("%lld\n", ans);
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &n);
    ~~~~~^~~~~~~~~~
building.cpp:51:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", h + i);
       ~~~~~^~~~~~~~~~~~~
building.cpp:54:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", w + i);
       ~~~~~^~~~~~~~~~~~~

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