ABC472を振り返る

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int n;
  cin >> n;
  vector<int> l(n);
  ll sum = 0;
  rep(i, 0, n) {
    cin >> l[i];
    sum += l[i];
  }
  ll half = sum / 2;

  ll le = 0, r = 0;
  int l_i = 0;
  rep(i, 0, n) {
    le += l[i];
    if (le >= half) {
      l_i = i;
      break;
    }
  }

  int r_i = 0;
  rrep(i, n - 1, 0) {
    r += l[i];
    if (r >= half) {
      r_i = i;
      break;
    }
  }

  if (le <= r) {
    cout << abs(le - (sum - le)) << "\n";
  } else {
    cout << abs(r - (sum - r)) << "\n";
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int n, m;
  ll k;
  cin >> n >> m >> k;
  vector<ll> a(n);
  vector<int> yn(n);
  rep(i, 0 , n){
    cin >> a[i];
  }

  ll cal = 0;
  rep(i, 0, n){
    if (i >= m - 1 && yn[i - m] == 0) {
      cal -= a[i - m];
    }
    if(cal + a[i] <= k){
      cal += a[i];
      yn[i] = 0;
      cout << "Yes" << "\n";
    }else{
      yn[i] = 1;
      cout << "No" << "\n";
    }
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> multi_source_bfs(int H, int W, const vector<string>& grid, const vector<pair<int, int>>& starts) {
  // dist配列を初期化(-1で未訪問を表す)
  vector<vector<int>> dist(H, vector<int>(W, -1));

  // 多視点BFS用のキュー
  queue<pair<int, int>> que;

  // 全ての始点をキューに投入し、距離0で初期化
  for (auto& st : starts) {
    dist[st.first][st.second] = 0;
    que.push(st);
  }

  // 方向ベクトル（上下左右）
  int dx[4] = {1, -1, 0, 0};
  int dy[4] = {0, 0, 1, -1};

  // BFSループ開始
  while (!que.empty()) {
    auto [x, y] = que.front();
    que.pop();

    for (int k = 0; k < 4; k++) {
      int nx = x + dx[k];
      int ny = y + dy[k];

      // 範囲チェック
      if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;

      // 壁マス('#')は通れないのでスキップ
      if (grid[nx][ny] == '#') continue;

      // すでに訪問済みならスキップ
      if (dist[nx][ny] != -1) continue;

      // 未訪問で通れるマスなら距離を更新
      dist[nx][ny] = dist[x][y] + 1;
      que.push({nx, ny});
    }
  }

  return dist;
}

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

  // 入力受け取り
  int H, W, k;
  cin >> H >> W >> k;
  vector<string> grid(H);
  vector<string> fie(H);
  vector<int> safeh(H, 0);
  vector<int> safew(W, 0);
  vector<vector<int>> way(H, vector<int>(W, -1));
  for (int i = 0; i < H; i++) {
    cin >> grid[i];
  }

  rep(i, 0, H) {
    rep(j, 0, W)  {
      if (grid[i][j] == '#') {
        safew[j] = 1;
        safeh[i] = 1;
      }
    }
  }

  rep(i, 0, H) {
    if (safeh[i] == 0) {
      rep(j, 0, W) {
        if (safew[j] == 0) {
          way[i][j] = 0;
        }
      }
    }
  }

  // 複数の始点を探し、ベクターに格納
  vector<pair<int, int>> starts;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (way[i][j] == 0) {
        starts.push_back({i, j});
      }
    }
  }

  // 多視点BFS実行
  vector<vector<int>> dist = multi_source_bfs(H, W, grid, starts);

  // 結果出力（各マスの距離を空白区切りで表示）
  // 到達不能なマスは -1 のまま
  ll ans = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cerr << dist[i][j] << (j == W - 1 ? '\n' : ' ');
      if (dist[i][j] <= k && dist[i][j] != -1) {
        ++ans;
      }
    }
  }

  cout << ans << "\n";

  return 0;
}