Submission #1023468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023468		avighna	Solar Storm (NOI20_solarstorm)	C++17	0 / 100	259 ms	125268 KiB

SolarStorm

#include <bits/stdc++.h>

typedef long long ll;

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

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

  std::vector<std::vector<int>> lift(n, std::vector<int>(21));
  for (int 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) {
      dist -= d[j - 1];
      j--;
    }
    lift[i][0] = std::min(n - 1, j + 1);
  }
  for (int bt = 1; bt <= 20; ++bt) {
    for (int 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 = [&](int l, int r) {
    ll ans = psum[r];
    if (l - 1 >= 0) {
      ans -= psum[l - 1];
    }
    return ans;
  };

  std::pair<ll, int> best;
  for (int i = 0; i < n; ++i) {
    int end = binary_lift(i, s);
    best = std::max(best, std::make_pair(sum(i, end), i));
  }

  std::vector<int> ans;
  for (int 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: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30