제출 #1214149

#제출 시각아이디문제언어결과실행 시간메모리
1214149avighnaSolar Storm (NOI20_solarstorm)C++20
100 / 100
1335 ms218664 KiB
#include <bits/stdc++.h>

typedef long long ll;

ll BinarySearchMin(ll s, ll e, const std::function<bool(ll)> &f) {
  ll ans = e;
  while (s <= e) {
    ll m = s + (e - s) / 2;
    if (f(m)) {
      ans = m;
      e = m - 1;
    } else {
      s = m + 1;
    }
  }
  return ans;
}

ll BinarySearchMax(ll s, ll e, const std::function<bool(ll)> &f) {
  ll ans = s;
  while (s <= e) {
    ll m = s + (e - s) / 2;
    if (f(m)) {
      ans = m;
      s = m + 1;
    } else {
      e = m - 1;
    }
  }
  return ans;
}

const ll N = 1e6 + 1;

ll d[N], v[N], pd[N], pv[N], left[N], right[N];
ll lift[N][20];

int main() {
  ll n, s, k;
  std::cin >> n >> s >> k;
  for (ll i = 2; i <= n; ++i) {
    std::cin >> d[i];
  }
  for (ll i = 1; i <= n; ++i) {
    std::cin >> v[i];
  }
  std::partial_sum(d, d + n + 1, pd);
  std::partial_sum(v, v + n + 1, pv);

  for (ll i = 1; i <= n; ++i) {
    left[i] = BinarySearchMin(1, i, [&](ll m) { return pd[i] - pd[m] <= k; });
    right[i] = BinarySearchMax(i, n, [&](ll m) { return pd[m] - pd[i] <= k; });
  }
  for (ll i = 1; i <= n; ++i) {
    lift[i][0] =
        BinarySearchMax(i, n, [&](ll m) { return left[m] - right[i] <= 1; });
  }
  for (int bt = 1; bt < 20; ++bt) {
    for (ll i = 1; i <= n; ++i) {
      lift[i][bt] = lift[lift[i][bt - 1]][bt - 1];
    }
  }

  std::pair<ll, ll> best;
  for (ll i = 1; i <= n; ++i) {
    ll j = i;
    for (int bt = 0; bt < 20; ++bt) {
      if ((s - 1) & (1 << bt)) {
        j = lift[j][bt];
      }
    }
    best = std::max(best, std::make_pair(pv[right[j]] - pv[left[i] - 1], i));
  }

  std::vector<ll> ans;
  for (ll i = 0, v = best.second; i < s; ++i) {
    ans.push_back(v);
    v = lift[v][0];
  }
  while (ans.size() >= 2 and ans[ans.size() - 1] == ans[ans.size() - 2]) {
    ans.pop_back();
  }
  std::cout << ans.size() << '\n';
  for (auto &i : ans) {
    std::cout << i << ' ';
  }
  std::cout << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...