Submission #1091650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091650		vjudge1	Potatoes and fertilizers (LMIO19_bulves)	C++17	0 / 100	1096 ms	24248 KiB

bulves

#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <utility>
#include <vector>

struct queue_2stack {
  std::vector<long long> s1, s2, min2;
  long long min1 = LLONG_MAX;

  void push(long long x) {
    s1.push_back(x);
    min1 = std::min(min1, x);
  }

  long long query_min() {
    ensure_s2_ready();
    return std::min(min2.back(), min1);
  }

  void pop() {
    ensure_s2_ready();
    s2.pop_back();
    min2.pop_back();
  }

  int size() {
    return (int) s1.size() + s2.size();
  }

  void debug() {
    std::cerr << "s2:"; for (int x: s2) std::cerr << " " << x; std::cerr << std::endl;
    std::cerr << "m2:"; for (int x: min2) std::cerr << " " << x; std::cerr << std::endl;
    std::cerr << "s1:"; for (int x: s1) std::cerr << " " << x; std::cerr << std::endl;
  }

  void ensure_s2_ready() {
    if (!s2.empty()) {
      return;
    }

    min1 = LLONG_MAX;
    while (!s1.empty()) {
      // pop one
      long long x = s1.back();
      s1.pop_back();
      // insert to s2
      s2.push_back(x);
      min2.push_back(x);
    }

    for (int i = min2.size() - 2; i >= 0; i--) {
      min2[i] = std::min(min2[i], min2[i + 1]);
    }
  }
};

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

  int n;
  std::cin >> n;

  std::vector<long long> dp(1, 0);
  std::vector<int> diff(n);
  long long ans = 0;
  long long total = 0;
  for (int i = 0; i < n; i++) {
    int a, b;
    std::cin >> a >> b;
    total += a - b;
    diff[i] = total > 0 ? -1 : 1;
    // subtask 1
    ans += std::abs(total);

    // subtask 3
    queue_2stack q;
    std::vector<long long> dp_nxt(dp.size() + a, LLONG_MAX);
    for (int j = 0; j < (int) dp.size() + a; j++) {
      if (j < dp.size()) {
        q.push(dp[j]);
      }
      dp_nxt[j] = q.query_min();
      if (j >= a) {
        q.pop();
      }
      // for (int k = std::max(0, j - a); k <= j && k < dp.size(); k++) {
      //   dp_nxt[j] = std::min(dp_nxt[j], dp[k]);
      // }
      dp_nxt[j] += std::abs(total - j);
    }
    // std::cerr << "take_min[" << i << "]:"; for (auto x: dp_nxt) std::cerr << " " << x; std::cerr << std::endl;
    // for (int j = 0; j < dp.size() + a; j++) {
    //   dp_nxt[j] += std::abs(total - j);
    // }
    // std::cerr << "dp[" << i << "]:"; for (auto x: dp_nxt) std::cerr << " " << x; std::cerr << std::endl;

    std::swap(dp, dp_nxt);
  }

  if (total == 1) {
    // subtask 2
    long long current = ans, total_diff = 0;
    while (!diff.empty()) {
      total_diff += diff.back();
      diff.pop_back();
      ans = std::min(ans, current + total_diff);
    }
  }

  // std::cout << ans << std::endl;
  std::cout << dp[total] << std::endl;
  return 0;
}

Compilation message (stderr)

bulves.cpp: In function 'int main()':
bulves.cpp:81:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |       if (j < dp.size()) {
      |           ~~^~~~~~~~~~~

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