#1190717 (C++23) No.3097 Azuki Kurai

• 問題: No.3097 Azuki Kurai
• ユーザー: wightou
• 提出日時: 2026-09-29 00:23:48
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 134 ms / 4,000 ms
• コード長: 3,376 bytes
• コンパイル時間: 4,790 ms
• コンパイル使用メモリ: 389,468 KB
• 実行使用メモリ: 15,664 KB
• 最終ジャッジ日時: 2026-09-29 00:23:57
• 合計ジャッジ時間: 7,705 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
other	AC * 32

ソースコード

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

constexpr long long INF = 1001001001001001001LL;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, m, k;
  cin >> n >> m >> k;

  vector<int> a(n);
  for (int i=0; i<n; i++) {
    cin >> a.at(i);
  }
  vector<int> b(m);
  for (int i=0; i<m; i++) {
    cin >> b.at(i);
    b.at(i)--;
  }

  //////////////// 出力変数定義 ////////////////

  vector<long long> result(m);

  //////////////////// 処理 ////////////////////

  // 最小費用流のフローネットワーク
  // j日目のi軒目は、基本的にj*n+i番、隣の家へ逃がす分がそれ+m*n
  // 2*m*nがソース、2*m*n+1がシンク
  mcf_graph<long long,long long> g(2*m*n+2);

  // 初日に持っている分の辺を張る
  for (int i=0; i<n; i++) {
    g.add_edge(2*m*n,i,a.at(i),0);
  }

  // 各日各家からの辺を張る
  for (int j=0; j<m; j++) {
    for (int i=0; i<n; i++) {

      // 妖怪が来る家は、コストを残りの夜の数として辺を張る
      // そうでない家は、次の日の自身へ（最終日はシンクへ）
      if (i==b.at(j)) g.add_edge(j*n+i,2*m*n+1,INF,m-j);
      else if (j==m-1) g.add_edge(j*n+i,2*m*n+1,INF,0);
      else  g.add_edge(j*n+i,(j+1)*n+i,INF,0);

      // 容量kまで他の家へ逃がせる
      g.add_edge(j*n+i,m*n+j*n+i,k,0);

      // 逃がす分は、妖怪が来ない隣家へ行く
      // 最終日は全体に安全に逃がせるので、シンクへ入れてしまう
      if (j!=m-1) {
        if ((i+1)%n!=b.at(j)) g.add_edge(m*n+j*n+i,(j+1)*n+(i+1)%n,k,0);
        if ((i+n-1)%n!=b.at(j)) g.add_edge(m*n+j*n+i,(j+1)*n+(i+n-1)%n,k,0);
      } else {
        g.add_edge(m*n+j*n+i,2*m*n+1,k,0);
      }
    }
  }

  // 最小費用流を求める
  //
  // j+1日目時点で最大に残す方法の中に、j日目まで最大に残せているケースが必ずある
  // これは、j日目にあえて最大にしないことでj+1日目以降の最大値が増えることがないことから明らか
  // 既存の各家保持量を減らさない範囲で、j日目に無駄に喰われる分を適当に流せばいいだけ
  //
  // 各日の残存数を同時に最大化できるため、その適切な重み付き総和を最大化すれば各日の残存数もそれぞれ最大になる
  // コスト設定を日付の逆順にしてあるため、各コスト辺の流量がその日に諦めざるを得ない量となる
  // 
  // p への代入はデバッグ用で、使用していない
  [[maybe_unused]] pair<long long,long long> p = g.flow(2*m*n,2*m*n+1);

  // 全ての辺の状況を取得し、各日にどのくらいロスしたかを調査
  vector<mcf_graph<long long,long long>::edge> es =  g.edges();
  vector<long long> lost(m,0);
  for (auto e : es) {
    if (e.cost==0) continue;
    lost.at(m-e.cost) = e.flow;
  }

  // 答えを順に求める
  long long sum = accumulate(a.begin(),a.end(),0LL);
  for (int i=0; i<m; i++) {
    sum -= lost.at(i);
    result .at(i) = sum;
  }

  //////////////////// 出力 ////////////////////

  for (size_t i=0; i<result.size(); i++) {
    cout << result.at(i) << endl;
  }

  //////////////////// 終了 ////////////////////

  return 0;

}