結果

問題 No.957 植林
ユーザー beetbeet
提出日時 2019-12-20 00:38:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,452 bytes
コンパイル時間 2,486 ms
コンパイル使用メモリ 215,028 KB
実行使用メモリ 26,040 KB
最終ジャッジ日時 2023-09-21 07:52:28
合計ジャッジ時間 48,481 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 145 ms
21,680 KB
testcase_04 AC 133 ms
20,416 KB
testcase_05 AC 120 ms
22,168 KB
testcase_06 AC 158 ms
23,412 KB
testcase_07 AC 128 ms
21,040 KB
testcase_08 AC 68 ms
22,036 KB
testcase_09 AC 63 ms
22,020 KB
testcase_10 AC 78 ms
23,476 KB
testcase_11 AC 70 ms
22,324 KB
testcase_12 AC 71 ms
21,864 KB
testcase_13 AC 53 ms
20,636 KB
testcase_14 AC 71 ms
23,924 KB
testcase_15 AC 66 ms
22,744 KB
testcase_16 AC 57 ms
19,924 KB
testcase_17 AC 59 ms
20,608 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 48 ms
25,128 KB
testcase_42 AC 49 ms
25,124 KB
testcase_43 AC 73 ms
25,324 KB
testcase_44 AC 83 ms
25,428 KB
testcase_45 AC 2 ms
4,380 KB
testcase_46 AC 1 ms
4,376 KB
testcase_47 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}



using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;

// AtCoder
const i64 CYCLES_PER_SEC = 2800000000;

struct Timer {
	i64 start;
	Timer(){reset();}
	void reset(){start=getCycle();}
	inline double get(){return (double)(getCycle()-start)/CYCLES_PER_SEC;}
	inline i64 getCycle(){
		u32 low,high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((i64)low)|((i64)high<<32);
	}
};

Timer timer;

template<typename T,bool directed>
struct Dinic{
  struct edge {
    int to;
    T cap;
    int rev;
    edge(){}
    edge(int to,T cap,int rev):to(to),cap(cap),rev(rev){}
  };

  vector<vector<edge> > G;
  vector<int> level,iter;

  Dinic(){}
  Dinic(int n):G(n),level(n),iter(n){}

  int add_edge(int from,int to,T cap){
    G[from].emplace_back(to,cap,G[to].size());
    G[to].emplace_back(from,directed?0:cap,G[from].size()-1);
    return G[to].back().rev;
  }

  void bfs(int s){
    fill(level.begin(),level.end(),-1);
    queue<int> que;
    level[s]=0;
    que.emplace(s);
    while(!que.empty()){
      int v=que.front();que.pop();
      for(int i=0;i<(int)G[v].size();i++){
        edge &e=G[v][i];
        if(e.cap>0&&level[e.to]<0){
          level[e.to]=level[v]+1;
          que.emplace(e.to);
        }
      }
    }
  }

  T dfs(int v,int t,T f){
    if(v==t) return f;
    for(int &i=iter[v];i<(int)G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[v]<level[e.to]){
        T d=dfs(e.to,t,min(f,e.cap));
        if(d==0) continue;
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    }
    return 0;
  }

  T flow(int s,int t,T lim){
    T fl=0;
    while(1){
      bfs(s);
      if(level[t]<0||lim==0) break;
      if(timer.get()>1.5) break;

      fill(iter.begin(),iter.end(),0);

      while(1){
        T f=dfs(s,t,lim);
        if(f==0) break;
        fl+=f;
        lim-=f;
      }
    }
    return fl;
  }

  T flow(int s,int t){
    return flow(s,t,numeric_limits<T>::max()/2);
  }

  T cut(int s,int t,int x,int a){
    static_assert(directed, "must be directed");
    auto &e=G[x][a];
    int y=e.to;
    T cr=G[y][e.rev].cap;
    if(cr==0) return e.cap=0;
    e.cap=G[y][e.rev].cap=0;
    T cap=cr-flow(x,y,cr);
    if(x!=s&&cap!=0) flow(x,s,cap);
    if(t!=y&&cap!=0) flow(t,y,cap);
    return cap;
  }

  T link(int s,int t,int x,int a,T f){
    auto &e=G[x][a];
    e.cap+=f;
    return flow(s,t,f);
  }
};


//INSERT ABOVE HERE
signed main(){
  int h,w;
  cin>>h>>w;
  vector< vector<int> > G(h,vector<int>(w));
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      cin>>G[i][j];

  vector<int> rs(h),cs(w);
  for(int i=0;i<h;i++) cin>>rs[i];
  for(int j=0;j<w;j++) cin>>cs[j];

  Dinic<long long, true> F(h*w+h+w+2);
  int S=h*w+h+w;
  int T=S+1;

  long long sum=0;
  for(int r:rs) sum+=r;
  for(int c:cs) sum+=c;

  const long long INF = 1e9+1;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      F.add_edge(S,i*w+j,G[i][j]);
      F.add_edge(i*w+j,h*w+i,INF);
      F.add_edge(i*w+j,h*w+h+j,INF);
    }
  }

  for(int i=0;i<h;i++) F.add_edge(h*w+i,T,rs[i]);
  for(int j=0;j<w;j++) F.add_edge(h*w+h+j,T,cs[j]);

  cout<<sum-F.flow(S,T)<<endl;
  return 0;
}
0