結果

問題 No.957 植林
ユーザー hitonanodehitonanode
提出日時 2019-12-19 23:22:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,841 bytes
コンパイル時間 1,894 ms
コンパイル使用メモリ 181,412 KB
実行使用メモリ 31,512 KB
最終ジャッジ日時 2024-07-07 02:06:44
合計ジャッジ時間 48,858 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
10,532 KB
testcase_01 AC 3 ms
10,592 KB
testcase_02 AC 3 ms
10,712 KB
testcase_03 AC 160 ms
26,528 KB
testcase_04 AC 121 ms
25,620 KB
testcase_05 AC 164 ms
27,248 KB
testcase_06 AC 110 ms
28,368 KB
testcase_07 AC 171 ms
25,972 KB
testcase_08 AC 85 ms
27,096 KB
testcase_09 AC 79 ms
28,012 KB
testcase_10 AC 85 ms
27,748 KB
testcase_11 AC 80 ms
27,388 KB
testcase_12 AC 97 ms
26,976 KB
testcase_13 AC 64 ms
24,936 KB
testcase_14 AC 84 ms
28,768 KB
testcase_15 AC 71 ms
27,232 KB
testcase_16 AC 66 ms
26,080 KB
testcase_17 AC 69 ms
25,708 KB
testcase_18 AC 1,470 ms
27,084 KB
testcase_19 AC 1,644 ms
27,492 KB
testcase_20 AC 1,623 ms
27,896 KB
testcase_21 AC 1,767 ms
28,660 KB
testcase_22 AC 1,913 ms
29,484 KB
testcase_23 AC 1,883 ms
29,580 KB
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 AC 1,437 ms
28,104 KB
testcase_32 AC 1,578 ms
27,360 KB
testcase_33 AC 1,594 ms
28,624 KB
testcase_34 AC 1,752 ms
28,660 KB
testcase_35 AC 1,911 ms
28,836 KB
testcase_36 AC 1,884 ms
29,736 KB
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 AC 21 ms
22,372 KB
testcase_42 AC 36 ms
30,104 KB
testcase_43 AC 26 ms
23,600 KB
testcase_44 AC 44 ms
30,100 KB
testcase_45 AC 4 ms
10,636 KB
testcase_46 AC 3 ms
10,676 KB
testcase_47 AC 4 ms
10,600 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
///// This part below is only for debug, not used /////
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
///// END /////

#define int long long
// <https://tjkendev.github.io/procon-library/cpp/max_flow/push-relabel-highest.html>
#define N 300*300 + 600 + 2 + 10

class PushRelabel {
  const lint inf = 1e18;
  int n;
  struct Edge {
    int to, cap, rev;
  };
  vector<Edge> g[N];

  int qs[N];
  int hs[N], ds[N], fs[N];
  bool active[N];
  vector<int> bs[N];
  int cur;

public:
  PushRelabel() {}
  PushRelabel(int n) { init(n); }
  inline void init(int n) { this->n = n; }

  inline void add_edge(int fr, int to, int cap) {
    g[fr].emplace_back(Edge{to, cap, (int) g[to].size()});
    g[to].emplace_back(Edge{fr, 0, (int) g[fr].size()-1});
  }

  inline int bfs(int t) {
    int a = 0, b = 1;
    for(int i=0; i<n; ++i) hs[i] = n, ds[i] = 0, bs[i].clear();
    qs[0] = t;
    hs[t] = 0; ds[0] = 1;
    cur = 0;
    int d = 0;
    while(a < b) {
      int v = qs[a++];
      d = hs[v];
      for(Edge &e : g[v]) {
        int w = e.to;
        if(hs[w] <= d + 1 || g[w][e.rev].cap == 0) continue;
        hs[w] = d + 1;
        if(active[w] && d+1 < n) {
          bs[d+1].push_back(w);
          cur = d+1;
        }
        if(d+1 < n) ++ds[d+1];
        qs[b++] = w;
      }
    }
    return d+1;
  }

  inline int flow(int s, int t) {
    for(int i=0; i<n; ++i) fs[i] = 0, active[i] = false;

    fs[s] = inf;
    active[s] = true;

    // initialize hs, bs, ds
    int gap = bfs(t);
    bs[cur].push_back(s);

    int cnt = 0;
    while(1) {
      while(cur >= 0 && bs[cur].size() == 0) --cur;
      if(cur < 0) break;

      int v = bs[cur].back(); bs[cur].pop_back();
      if(v == t) continue;

      int hv = hs[v];
      // Gap-relabeling
      if(hv > gap) {
        if(hv < n) --ds[hv];
        hs[v] = n;
        continue;
      }


      // push
      int rest = fs[v];
      for(Edge &e : g[v]) {
        int w = e.to;
        if(e.cap > 0 && hv > hs[w] && hs[w] < gap) {
          int d = min(rest, e.cap);
          e.cap -= d;
          g[w][e.rev].cap += d;
          rest -= d;
          fs[w] += d;
          if(!active[w]) {
            int hw = hs[w];
            bs[hw].push_back(w);
            if(cur < hw) cur = hw;
            active[w] = true;
          }
          if(rest == 0) break;
        }
      }
      fs[v] = rest;

      if(rest == 0) {
        active[v] = false;
        continue;
      }

      // relabel
      int h0 = hs[v];
      hv = n;
      for(Edge &e : g[v]) {
        int w = e.to;
        if(e.cap > 0 && hv > hs[w] + 1 && hs[w] < gap) {
          hv = hs[w] + 1;
        }
      }
      if(h0 != hv) {
        --ds[h0];
        if(ds[h0] == 0 && h0 < gap) {
          gap = h0;
          hv = n;
        } else if(hv == gap) {
          ++gap;
        }
        if(hv < n) ++ds[hv];
      }

      hs[v] = hv;
      if(hv < n) {
        bs[hv].push_back(v);
        if(cur < hv) cur = hv;
      } else {
        active[v] = false;
      }

      if((++cnt) % n == 0) {
        gap = bfs(t);
      }
    }
    return fs[t];
  }

};
PushRelabel g;

signed main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<lint>> G(H, vector<lint>(W));
    cin >> G;
    vector<lint> R(H), C(W);
    cin >> R >> C;
    int Z = 1 + H + W + H * W;
    g.init(Z + 1);
    REP(i, H) if (R[i]) g.add_edge(0, i + 1,R[i]);
    REP(j, W) if (C[j]) g.add_edge(0, H + 1 + j, C[j]);
    REP(i, H) REP(j, W) {
        int b = H + W + 1 + i * W + j;
        if (G[i][j] < R[i] + C[j])
        {
            g.add_edge(i + 1, b, 1e10);
            g.add_edge(H + 1 + j, b, 1e10);
            g.add_edge(b, Z, G[i][j]);
        }
        else
        {
            g.add_edge(i + 1, Z, 1e10);
            g.add_edge(H + j + 1, Z, 1e10);
        }
    }
    lint f = g.flow(0, Z);
    cout << accumulate(ALL(R), 0LL) + accumulate(ALL(C), 0LL) - f << endl;
}
0