Submission #1023495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023495		avighna	Solar Storm (NOI20_solarstorm)	C++17	15 / 100	718 ms	248860 KiB

SolarStorm

#include <bits/stdc++.h>

typedef long long ll;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, s, k;
  std::cin >> n >> s >> k;

  if (n == 1) {
    std::cout << "wha\n";
    return 0;
  }

  std::vector<ll> d(n - 1), v(n);
  for (auto &i : d) {
    std::cin >> i;
  }
  for (auto &i : v) {
    std::cin >> i;
  }

  std::vector<std::vector<ll>> lift(n, std::vector<ll>(21));
  std::vector<ll> right(n);
  for (ll i = n - 1, j = n - 1, dist = 0; i >= 0; --i) {
    if (i != n - 1) {
      dist += d[i];
    }
    // j is the last index satisfying dist[i...j] <= k
    while (dist > k and j - 1 >= 0) {
      dist -= d[j - 1];
      j--;
    }
    lift[i][0] = std::min(n - 1, j + 1);
    right[i] = j;
  }
  std::vector<ll> left(n);
  for (ll i = 0, j = 0, dist = 0; i < n; ++i) {
    if (i != 0) {
      dist += d[i - 1];
    }
    while (dist > k and j < n - 1) {
      dist -= d[j];
      j++;
    }
    left[i] = j;
  }
  for (ll bt = 1; bt <= 20; ++bt) {
    for (ll i = 0; i < n; ++i) {
      lift[i][bt] = lift[lift[i][bt - 1]][bt - 1];
    }
  }

  auto binary_lift = [&](ll node, ll k) {
    for (ll bt = 0; bt <= 20; ++bt) {
      if (k & (1 << bt)) {
        node = lift[node][bt];
      }
    }
    return node;
  };

  std::vector<ll> psum(n);
  std::partial_sum(v.begin(), v.end(), psum.begin());
  auto sum = [&](ll l, ll r) {
    ll ans = psum[r];
    if (l - 1 >= 0) {
      ans -= psum[l - 1];
    }
    return ans;
  };

  std::pair<ll, ll> best = {0, 0};
  for (ll i = 0; i < n; ++i) {
    best = std::max(
        best, std::make_pair(sum(left[i], right[binary_lift(i, s - 1)]), i));
  }

  std::vector<ll> ans;
  for (ll i = 0, node = best.second; i < s; ++i) {
    ans.push_back(node);
    node = lift[node][0];
  }
  while (ans.size() >= 2 and ans.back() == ans[ans.size() - 2]) {
    ans.pop_back();
  }
  std::cout << ans.size() << "\n";
  for (auto &i : ans) {
    std::cout << i + 1 << " ";
  }
  std::cout << "\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 7 / 7
• Subtask 3: 0 / 11
• Subtask 4: 8 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30