fork download
copy 
  1. // #pragma GCC optimize("Ofast")
  2. // #pragma GCC optimize ("unroll-loops")
  3. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #include<bits/stdc++.h>
  5. #define ll long long
  6. #define f(i,a,b) for(ll i=a;i<b;i++)
  7. #define mod 1000000007
  8. #define mod2 1000000009
  9. #define mod3 1000000021
  10. #define pie 3.14159265359
  11. #define mp make_pair
  12. #define ff first
  13. #define ss second
  14. #define rf(i,a,b) for(ll i=a;i>=b;i--)
  15. #define sc(a) scanf("%lld",&a)
  16. #define pf printf
  17. #define sz(a) (ll)(a.size())
  18. #define psf push_front
  19. #define ppf pop_front
  20. #define ppb pop_back
  21. #define pb push_back
  22. #define pq priority_queue
  23. #define all(s) s.begin(),s.end()
  24. #define sp(a) setprecision(a)
  25. #define rz resize
  26. #define ld long double
  27. #define inf 1e15
  28. #define ub upper_bound
  29. #define lb lower_bound
  30. #define bs binary_search
  31. #define eb emplace_back
  32. #define out fflush(stdout);
  33.  
  34. using namespace std;
  35.  
  36. int r,c;
  37. double error=1e-9;
  38.  
  39. bool check(int i, int j)
  40. {
  41. 	if(i<=r && j<=c && i>0 && j>0)
  42. 		return 1;
  43. 	else
  44. 		return 0;
  45. }
  46.  
  47. int main()
  48. {
  49. 	ios_base::sync_with_stdio(false);
  50. 	cin.tie(NULL);
  51. 	// freopen("input.txt","r",stdin);
  52.     // freopen("output.txt","w",stdout);
  53. 	int t;
  54. 	cin>>t;
  55. 	f(i,1,t+1)
  56. 	{
  57. 		cout<<"Case #"<<i<<": ";
  58. 		cin>>r>>c;
  59. 		vector<vector<ll> > a(r+1,vector<ll> (c+1));
  60. 		ll sum=0,ans=0;
  61. 		vector<set<int> > s_row(r+2),s_col(c+2);
  62. 		set<int> s3;
  63. 		f(i,1,r+1)
  64. 		{
  65. 			s3.insert(i);
  66. 			f(j,1,c+1)
  67. 			{
  68. 				cin>>a[i][j];
  69. 				s_row[i].insert(j);
  70. 				s_col[j].insert(i);
  71. 				sum+=a[i][j];
  72. 			}
  73. 		}
  74. 		f(i,1,c+1)
  75. 			s_col[i].insert(r+1),s_col[i].insert(0);
  76. 		f(i,1,r+1)
  77. 			s_row[i].insert(c+1),s_row[i].insert(0);
  78. 		bool flag=1;
  79. 		int dx[]={1,0,-1,0};
  80. 		int dy[]={0,1,0,-1};
  81. 		while(flag)
  82. 		{
  83. 			flag=0;
  84. 			ans+=sum;
  85. 			vector<pair<int,int> > temp,temp2;
  86. 			f(i,1,r+1)
  87. 			{
  88. 				auto it=s_row[i].begin(),it3=s_row[i].end();
  89. 				it++,it3--;
  90. 				for(;it!=it3;it++)
  91. 				{
  92. 					int j=(*it);
  93. 					double tot=0;
  94. 					int cnt=0;
  95. 					f(k,0,4)
  96. 					{
  97. 						int x,y;
  98. 						auto it2=s_col[j].lb(i);
  99. 						x=i,y=j;
  100. 						if(dy[k]==1)
  101. 						{
  102. 							it++;
  103. 							x=i,y=(*it);
  104. 							it--;
  105. 						}
  106. 						else if(dy[k]==-1)
  107. 						{
  108. 							it--;
  109. 							x=i,y=(*it);
  110. 							it++;
  111. 						}
  112. 						if(dx[k]==1)
  113. 						{
  114. 							it2++;
  115. 							x=(*it2),y=j;
  116. 							it2--;
  117. 						}
  118. 						else if(dx[k]==-1)
  119. 						{
  120. 							it2--;
  121. 							x=(*it2),y=j;
  122. 							it2++;
  123. 						}
  124. 						if(check(x,y) && a[x][y]!=0)
  125. 						{
  126. 							cnt++,tot+=a[x][y];
  127. 							// cout<<"Values: "<<tot<<' '<<cnt<<endl;
  128. 						}
  129. 					}
  130. 					if(cnt!=0)
  131. 					{
  132. 						double val=tot/cnt;
  133. 						if(val>a[i][j])
  134. 						{
  135. 							flag=1;
  136. 							temp.eb(mp(i,j));
  137. 							sum-=a[i][j];
  138. 							// cout<<"Sum: "<<ans<<' '<<sum<<' '<<val<<' '<<i<<' '<<j<<"\n";
  139. 						}
  140. 					}
  141. 					else
  142. 					{
  143. 						// cout<<i<<' '<<j<<endl;
  144. 						temp2.eb(mp(i,j));
  145. 					}
  146. 				}
  147. 			}
  148. 			// f(i,0,sz(temp2))
  149. 			// 	cout<<temp2[i].ff<<' '<<temp2[i].ss<<endl;
  150. 			f(i,0,sz(temp))
  151. 			{
  152. 				// cout<<"Ent"<<endl;
  153. 				s_row[temp[i].ff].erase(s_row[temp[i].ff].lb(temp[i].ss)),s_col[temp[i].ss].erase(s_col[temp[i].ss].lb(temp[i].ff));
  154. 				a[temp[i].ff][temp[i].ss]=0;
  155. 				if(s_row[temp[i].ff].empty())
  156. 					s3.erase(temp[i].ff);
  157. 			}
  158. 			f(i,0,sz(temp2))
  159. 			{
  160. 				s_row[temp2[i].ff].erase(s_row[temp2[i].ff].lb(temp2[i].ss)),s_col[temp2[i].ss].erase(s_col[temp2[i].ss].lb(temp2[i].ff));			
  161. 				if(s_row[temp2[i].ff].empty())
  162. 					s3.erase(temp2[i].ff);
  163. 			}
  164. 		}
  165. 		cout<<ans<<"\n";
  166. 	}
  167. }
Success #stdin #stdout 0s 4348KB
comments (?)
stdin
copy 
4
1 1
15
3 3
1 1 1
1 2 1
1 1 1
1 3
3 1 2
1 3
1 2 3
stdout
copy 
Case #1: 15
Case #2: 16
Case #3: 14
Case #4: 14
https://ideone.com/6l4PWy
language:
C++14 (gcc 8.3)
created:
3 years 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!