結果

問題 No.3097 Azuki Kurai
コンテスト
ユーザー wightou
提出日時 2026-09-28 23:40:24
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 134 ms / 4,000 ms
+ 402µs
コード長 1,795 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,123 ms
コンパイル使用メモリ 393,640 KB
実行使用メモリ 15,388 KB
最終ジャッジ日時 2026-09-28 23:40:33
合計ジャッジ時間 7,961 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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);

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

  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);
      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);
      }
    }
  }

  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(e.from/n) = 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;

}
0