제출 #1091351

#제출 시각아이디문제언어결과실행 시간메모리
1091351Trisanu_DasSolar Storm (NOI20_solarstorm)C++17
62 / 100
2021 ms53064 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
 
int dist[N], valor[N], jump[N];
vector<int> sum, dp;
 
signed main () {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, s, k;
  cin >> n >> s >> k;
  sum.resize(n);
  dp.resize(n);
  for (int i = 0; i < n - 1; i++) {
    cin >> dist[i];
    if (i) sum[i] = sum[i - 1] + dist[i - 1];
  }
  for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + dist[i - 1];
  for (int i = 0; i < n; i++) {
    cin >> valor[i];
    dp[i] += valor[i];
    if (i) dp[i] += dp[i - 1];
  }
  int mx = -1, best_start = -1;
  for (int i = 0; i < n; i++) jump[i] = upper_bound (sum.begin(), sum.end(), sum[i] + k) - sum.begin();
  for (int i = 0; i < n; i++) {
    int cur = 0, shield_left = s;
    for (int hi = i; hi < n && shield_left > 0; ) {
      int nxt = jump[hi] - 1;
      int esq = dp[nxt] - (hi - 1 >= 0 ? dp[hi - 1] : 0);
      cur += esq;
      int nxtnxt = jump[nxt] - 1;
      int dir = dp[nxtnxt] - dp[nxt];
      cur += dir;
      hi = nxtnxt + 1;
      --shield_left;
    }
    if (cur > mx) {
      mx = cur;
      best_start = i;
    }
  }
  vector<int> ans;
  int shield_left = s;
  for (int hi = best_start; hi < n && shield_left > 0; ) {
    int nxt = jump[hi] - 1;
    ans.emplace_back(nxt);
    int nxtnxt = jump[nxt] - 1;
    hi = nxtnxt + 1;
    --shield_left;
  }
  cout << (int) ans.size() << '\n';
  for (auto to : ans) cout << to + 1 << ' ';
}
#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...