Submission #1091918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091918		vjudge1	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	217 ms	19124 KiB

bulves

#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

int main() {
  std::cin.tie(NULL)->sync_with_stdio(false);

  int n;
  std::cin >> n;

  // ans = sum abs(prefix(a - c, i)) where c[] = final configuration
  // c[i] = b[i] + x[i], where x[i] = some fertilizers we remove from position i
  // so ans = sum abs(prefix(a - b, i) - prefix(x, i)) and we want to minimize this
  // DP[i][x] = minimize ans with x = prefix(x, i)
  // DP[i][x] = min(DP[i-1][y] + abs(prefix(a - b, i) - x, 0 <= x - y <= a[i]) 
  //  - here x = prefix(x, i) and y = prefix(x, i-1), and x[i] = x - y
  //  - range x[i] is [0, a[i]] -> 0 <= x - y <= a[i]
  // Transform DP: DP[i][x] = min(DP[i-1][y], max(0, x-a[i]) <= y <= x) + abs(prefix(a - b, i) - x)
  // we can do slope trick here as inductively it is convex linear
  long long total = 0;
  long long m = 0, c = 0; // leftmost m & c
  long long shift = 0;
  std::priority_queue<long long> pq_neg;
  std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pq_pos;
  for (int i = 0; i < n; i++) {
    long long a, b;
    std::cin >> a >> b;

    total += a - b;

    // take min: shift positive grad all by a
    if (!pq_pos.empty()) {
      shift += a;
    }

    // insert
    if (total > 0) {
      // combine with y = total - x
      m--;
      c += total;
      pq_neg.push(total);
      pq_pos.push(total - shift);
    } else {
      // combine with y = x + (-total) if x >= 0, else -x -total
      m--;
      c += -total;
      pq_neg.push(0);
      pq_pos.push(-shift);
    }

    // normalize
    while (pq_neg.top() > pq_pos.top() + shift) {
      long long x_neg = pq_neg.top();
      long long x_pos = pq_pos.top() + shift;
      pq_neg.pop();
      pq_pos.pop();

      pq_neg.push(x_pos);
      pq_pos.push(x_neg - shift);
    }
  }

  // reorder pq_neg
  std::vector<long long> xs(pq_neg.size());
  while (!pq_neg.empty()) {
    long long x = pq_neg.top();
    pq_neg.pop();
    xs[pq_neg.size()] = x;
  }
  for (long long x: xs) {
    if (x > total) {
      std::cout << m * total + c << std::endl;
      return 0;
    }
    m++;
    c -= x;
  }

  while (!pq_pos.empty()) {
    long long x = pq_pos.top() + shift;
    pq_pos.pop();
    if (x > total) {
      std::cout << m * total + c << std::endl;
      return 0;
    }
    m++;
    c -= x;
  }

  std::cout << m * total + c << std::endl;

  return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36