Submission #224723

#	Time	Username	Problem	Language	Result	Execution time	Memory
224723		Haunted_Cpp	Solar Storm (NOI20_solarstorm)	C++17	8 / 100	232 ms	38624 KiB

SolarStorm

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cassert>
 
typedef long long i64;
using namespace std;

const int N = 1e6 + 5;

int dist [N], valor [N];
i64 sum [N];
i64 dp [N];

bitset<N> has_shield;

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, s;
  i64 k;
  cin >> n >> s >> k;
  for (int i = 0; i < n - 1; i++) {
    cin >> dist[i];
    if (i) {
      sum[i] = sum[i - 1] + dist[i - 1];
    }
  }
  i64 tot = 0;
  for (int i = 0; i < n; i++) {
    cin >> valor[i];
    tot += valor[i];
    dp[i] += valor[i];
    if (i) dp[i] += dp[i - 1];
  }
  // Solving K = 1
  int best_start = -1;
  i64 mx = 0;
  for (int i = 0; i < n; i++) {
    i64 cur = (i + s - 1 >= n ? tot : dp[i + s - 1]) - (i - 1 >= 0 ? dp[i - 1] : 0);
    if (cur > mx) {
      mx = cur;
      best_start = i;
    }
  }
  vector<i64> ans;
  i64 shield_left = s;
  for (int hi = best_start; hi < min (n, best_start + s); hi++) {
    if (hi >= n) break;
    ans.emplace_back(hi);
    --shield_left;
  }
  cout << (int) ans.size() << '\n';
  for (auto to : ans) cout << to + 1 << ' ';
  return 0;
}

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