Submission #224678

#	Time	Username	Problem	Language	Result	Execution time	Memory
224678		Haunted_Cpp	Solar Storm (NOI20_solarstorm)	C++17	0 / 100	580 ms	46416 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];
    }
  }
  for (int i = 0; i < n; i++) {
    cin >> valor[i];
    dp[i] += valor[i];
    if (i) dp[i] += dp[i - 1];
  }
  sum[n - 1] = sum[n] = sum[n - 2]; 
  dp[n] = dp[n - 1];
  int shield_left = s, lo = 0, hi = 0, start_place = -1;
  i64 mx = -1, cur = 0;
  while (hi < n) {
    cout << lo << ' ' << hi << ' ' << cur << ' ' << shield_left << '\n';
    mx = max (mx, cur);
    if (shield_left > 0) {
      // Vamos expandir o limite direito
      assert (has_shield[hi] == 0);
      has_shield[hi] = 1;
      shield_left -= has_shield[hi];
      // O nxt lugar sera o nao protegido por este shield, ou seja, 
      int nxt = (upper_bound (sum, sum + n, sum[hi] + k) - sum);   
      // Adicionar o score
      cur += (dp[nxt - 1] - (hi - 1 >= 0 ? dp[hi - 1] : 0)); 
      // Mover o right pointer
      hi = nxt;
    } else {
      // Vamos mover o limite esquerdo
      assert (has_shield[lo] == 1);
      shield_left += has_shield[lo];
      has_shield[lo] = 0;
      // Vamos remover os da esquerda do lo
      int p = (lower_bound (sum, sum + n, sum[lo] - k) - sum);
      cur -= (dp[lo] - (p - 1 >= 0 ? dp[p] : 0));  
      // Vamos mover apenas para a direita 1x
      int nxt = lo + 1;
      // Vamos adicionar o nxt
      lo = nxt;
      if (has_shield[lo] == 0) {
        p = (lower_bound (sum, sum + n, sum[lo] - k) - sum);
        cur += (dp[lo] - (p - 1 >= 0 ? dp[p] : 0)); 
        has_shield[lo] = 1;
        shield_left -= has_shield[lo];
      }
    }
  }
  mx = max (mx, cur);
  cout << mx << '\n';
  cout << start_place << '\n';
  return 0;
}

• 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