Submission #1023547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023547		avighna	Solar Storm (NOI20_solarstorm)	C++17	36 / 100	403 ms	209652 KiB

SolarStorm

#include <iostream>
#include <numeric>
#include <vector>
 
typedef long long ll;
 
const ll N = 1e6 + 1;
 
ll d[N], v[N], left[N], right[N], psum[N];
ll lift[N][20];
 
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
 
  ll n, s, k;
  std::cin >> n >> s >> k;
 
  for (ll i = 0; i < n - 1; ++i) {
    std::cin >> d[i];
  }
  for (ll i = 0; i < n; ++i) {
    std::cin >> v[i];
  }
 
  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] = j + 1;
    right[i] = j;
  }
  right[n] = n - 1;
  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;
  }
  lift[n][0] = n;
  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::partial_sum(v, v + n, psum);
  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;
  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, node = lift[node][0]) {
    ans.push_back(node);
  }
  while (!ans.empty() and ans.back() == n) {
    ans.pop_back();
  }
  std::cout << ans.size() << "\n";
  for (auto &i : ans) {
    std::cout << i + 1 << " ";
  }
  std::cout << "\n";
}

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