fork download 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define file freopen("BOARD.inp", "r", stdin); freopen("BOARD.out", "w", stdout);
  4. #define toiuu ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. #define gh 1000000005
  6. #define xRay signed main()
  7. using namespace std;
  8. struct meoo{int to,rr,cc;};
  9. class mm{
  10. public:
  11. 	vector<vector<meoo>>d;
  12. 	vector<int>h,k;
  13. 	mm(int n):d(n),h(n),k(n){}
  14. 	void jack(int oi,int io,int cc){
  15. 		d[oi].push_back({io,(int)d[io].size(),cc});
  16. 		d[io].push_back({oi,(int)d[oi].size()-1,0});
  17. 	}
  18. 	bool bbb(int s,int t){
  19. 		fill(h.begin(),h.end(),-1);
  20. 		queue<int>q;
  21. 		h[s]=0;
  22. 		q.push(s);
  23. 		while(!q.empty()){
  24. 			int v=q.front();q.pop();
  25. 			for(auto&e:d[v]){
  26. 				if(e.cc>0&&h[e.to]<0){
  27. 					h[e.to]=h[v]+1;
  28. 					q.push(e.to);
  29. 				}
  30. 			}
  31. 		}
  32. 		return h[t]>=0;
  33. 	}
  34. 	int ddd(int v,int t,int f){
  35. 		if(v==t)return f;
  36. 		for(int&i=k[v];i<d[v].size();++i){
  37. 			meoo&e=d[v][i];
  38. 			if(e.cc>0&&h[v]<h[e.to]){
  39. 				int ow=ddd(e.to,t,min(f,e.cc));
  40. 				if(ow>0){
  41. 					e.cc-=ow;
  42. 					d[e.to][e.rr].cc+=ow;
  43. 					return ow;
  44. 				}
  45. 			}
  46. 		}
  47. 		return 0;
  48. 	}
  49. 	int ww(int s,int t){
  50. 		int y=0;
  51. 		while(bbb(s,t)){
  52. 			fill(k.begin(),k.end(),0);
  53. 			int f;
  54. 			while((f=ddd(s,t,gh))>0)y+=f;
  55. 		}
  56. 		return y;
  57. 	}
  58. };
  59. xRay{
  60. 	toiuu;
  61. 	file;
  62. 	int n,m;cin>>n>>m;
  63. 	for(int _=0;_<1000000;++_);
  64. 	vector<vector<int>>a(n,vector<int>(m));
  65. 	for(auto&o:a)for(auto&z:o)cin>>z;
  66. 	int tl=2+2*n*m;
  67. 	mm mf(tl);
  68. 	int se=0,ni=1,of=0;
  69. 	for(auto&o:a)for(auto&z:o)if(z<0)of+=-z;
  70. 	int s[]={-1,1,0,0},ss[]={0,0,-1,1};
  71. 	for(int i=0;i<n;++i)
  72. 		for(int j=0;j<m;++j){
  73. 			int in=2*(i*m+j)+2;
  74. 			int au=in+1;
  75. 			if(a[i][j]>=0){
  76. 				mf.jack(in,au,a[i][j]);
  77. 			}else{
  78. 				mf.jack(se,in,-a[i][j]);
  79. 				mf.jack(au,ni,-a[i][j]);
  80. 			}
  81. 			for(int d=0;d<4;++d){
  82. 				int ni=i+s[d],nj=j+ss[d];
  83. 				if(ni>=0&&ni<n&&nj>=0&&nj<m){
  84. 					int an=2*(ni*m+nj)+2;
  85. 					mf.jack(au,an,gh);
  86. 				}
  87. 			}
  88. 		}
  89. 	for(int i=0;i<n;++i)
  90. 		for(int j=0;j<m;++j){
  91. 			int in=2*(i*m+j)+2;
  92. 			int au=in+1;
  93. 			if(a[i][j]>=0){
  94. 				if((i+j)%2==0)mf.jack(se,in,gh);
  95. 				else mf.jack(au,ni,gh);
  96. 			}
  97. 		}
  98. 	int son=0;
  99. 	for(auto&o:a)for(auto&z:o)if(z>0)son+=z;
  100. 	int mi=mf.ww(se,ni);
  101. 	cout<<(son-mi)<<'\n';
  102. 	return 0;
  103. }
  104.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/2uw1KZ
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!