Submission #767899

#	Time	Username	Problem	Language	Result	Execution time	Memory
767899		Andrei_Calota	Building Bridges (CEOI17_building)	C++14	100 / 100	92 ms	17944 KiB

building

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

const int N_MAX = 1e5;
const int VALUE_MAX = 1e6;

int64 h[1 + N_MAX], w[1 + N_MAX];
int n; int64 pSum[1 + N_MAX];

void initInput (void) {
    cin >> n;
    for (int i = 1; i <= n; i ++)
       cin >> h[i];
    for (int i = 1; i <= n; i ++)
       cin >> w[i];
    for (int i = 1; i <= n; i ++)
       pSum[i] = pSum[i - 1] + w[i];
}

struct defLine {
    int64 slope, h;
    int64 getEval (int64 t) {return slope * t + h;}
};

const int64 myINF = 1e18;
struct LiChaoNode {
    defLine line;
    LiChaoNode* u;
    LiChaoNode* v;

    LiChaoNode () {
       line = {0, +myINF};
       u = NULL; v = NULL;
    }
};

void update (LiChaoNode* root, int left, int right, defLine newLine) {
    if (left == right) {
      if (root -> line.getEval (left) > newLine.getEval (left))
        swap (root -> line, newLine);
    }
    else {
      int mid = left + (right - left) / 2;
      if (root -> line.getEval (mid) > newLine.getEval (mid))
        swap (root -> line, newLine);
      if (root -> line.slope < newLine.slope) {
        if (root -> u == NULL)
          root -> u = new LiChaoNode;
        update (root -> u, left, mid, newLine);
      }
      else {
        if (root -> v == NULL)
          root -> v = new LiChaoNode;
        update (root -> v, mid + 1, right, newLine);
      }
    }
}

int64 query (LiChaoNode* root, int left, int right, int64 t) {
    if (left == right)
      return root -> line.getEval (t);
    int mid = left + (right - left) / 2;
    int64 answer = root -> line.getEval (t);
    if (t <= mid && root -> u != NULL)
      answer = min (answer, query (root -> u, left, mid, t));
    else if (root -> v != NULL)
      answer = min (answer, query (root -> v, mid + 1, right, t));
    return answer;
}

int64 DP[1 + N_MAX];
void solve (void) {
    LiChaoNode* CHT = new LiChaoNode;
    DP[1] = 0; update (CHT, 0, VALUE_MAX, {-2 * h[1], DP[1] + h[1] * h[1] - w[1]});

    for (int i = 2; i <= n; i ++) {
       DP[i] = h[i] * h[i] + pSum[i - 1] + query (CHT, 0, VALUE_MAX, h[i]);
       defLine newLine = {-2 * h[i], DP[i] + h[i] * h[i] - pSum[i]};
       update (CHT, 0, VALUE_MAX, newLine);
       ///cout << DP[i] << "\n";
    }
    cout << DP[n];
}
int main()
{
   initInput ();
   solve ();
    return 0;
}

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