Submission #1091802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091802		vjudge1	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	391 ms	54096 KiB

bulves

#include <climits>
#include <iostream>
#include <set>

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

  int n;
  std::cin >> n;

  long long total = 0;
  long long m = 0, c = 0; // leftmost m & c
  long long shift = 0;
  std::multiset<long long> m_neg, m_pos;
  auto calc_y = [&](long long x) -> long long {
    long long cc = c, mm = m;
    long long xnow = LLONG_MIN;
    for (auto xx: m_neg) {
      if (xx > x) {
        // std::cerr << "x=" << x << " m=" << mm << " c=" << cc << std::endl;
        return mm * x + cc;
      }
      // mm * x + cc = (mm + 1) * x + (cc - x)
      mm++;
      cc -= xx;
    }
    for (auto xx: m_pos) {
      xx += shift;
      if (xx > x) {
        // std::cerr << "x=" << x << " m=" << mm << " c=" << cc << std::endl;
        return mm * x + cc;
      }
      mm++;
      cc -= xx;
    }
    return mm * x + cc;
  };


  for (int i = 0; i < n; i++) {
    long long a, b;
    std::cin >> a >> b;

    total += a - b;

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

    // insert
    if (total > 0) {
      // TODO: combine with y = total - x
      m--;
      c += total;
      m_neg.insert(total);
      m_pos.insert(total - shift);
    } else {
      // TODO: combine with y = x + (-total) if x >= 0, else -x -total
      m--;
      c += -total;
      m_neg.insert(0);
      m_pos.insert(-shift);
    }

    // normalize
    while (*m_neg.rbegin() > *m_pos.begin() + shift) {
      long long x_neg = *m_neg.rbegin();
      long long x_pos = *m_pos.begin();
      m_neg.erase(--m_neg.end());
      m_pos.erase(m_pos.begin());

      m_neg.insert(x_pos + shift);
      m_pos.insert(x_neg - shift);
    }

    // debug
    // std::cerr << std::endl;
    // std::cerr << "m=" << m << " c:" << c << std::endl;
    // std::cerr << "m_neg:"; for (auto x: m_neg) std::cerr << " " << x; std::cerr << std::endl;
    // std::cerr << "m_pos:"; for (auto x: m_pos) std::cerr << " " << x + shift; std::cerr << std::endl;
    // for (int j = 0; j < 10; j++) std::cerr << " " << calc_y(j); std::cerr << std::endl;
  }

  std::cout << calc_y(total) << std::endl;

  return 0;
}

Compilation message (stderr)

bulves.cpp: In lambda function:
bulves.cpp:17:15: warning: unused variable 'xnow' [-Wunused-variable]
   17 |     long long xnow = LLONG_MIN;
      |               ^~~~

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