fork download
copy 
  1. // #pragma GCC target ("avx2")
  2. // #pragma GCC optimization ("O3")
  3. // #pragma GCC optimization ("unroll-loops")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. #define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. // #define int long long int
  8. #define ll int
  9. #define bits_count __builtin_popcountll
  10. #define endl '\n'
  11. #define double long double
  12. #define ld double
  13. #define FOR(i,a,n) for (ll i=(a);i<=(n);++i)
  14. #define RFOR(i,a,n) for (ll i=(n);i>=(a);--i)
  15. #define FI(i,n) for (ll i=0; i<(n); ++i)
  16. #define ZERO(a) memset((a),0,sizeof((a)))
  17. #define MINUS(a) memset((a),-1,sizeof((a)))
  18. #define f first
  19. #define s second
  20. #define pb push_back
  21. #define mk make_pair
  22. #define all(g) g.begin(),g.end()
  23. #define sz(x) (ll)x.size()
  24. #define pr pair<int,int>
  25. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  26. int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }
  27.  
  28. // #include <ext/pb_ds/assoc_container.hpp> // Common file
  29. // #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
  30. // using namespace __gnu_pbds;
  31. // typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  32.  
  33.  
  34. void solve(){
  35.  
  36.     int n,m; cin>>n>>m;
  37.     vector<vector<int>> a(n+1,vector<int>(m+1));
  38.     set<int> rows[n+1];
  39.     set<int> columns[m+1];
  40.  
  41.     FOR(i,1,n) FOR(j,1,m) cin>>a[i][j];
  42.  
  43.     int skillsum = 0;
  44.     FOR(i,1,n) FOR(j,1,m) skillsum += a[i][j];
  45.     int ans = skillsum;
  46.  
  47.     FOR(i,1,n) FOR(j,1,m) rows[i].insert(j);
  48.     FOR(j,1,m) FOR(i,1,n) columns[j].insert(i);
  49.  
  50.     set<pair<int,int>> que;
  51.  
  52.     FOR(i,1,n){
  53.         FOR(j,1,m){
  54.  
  55.             int cnt = 0,sum = 0;
  56.             auto right = rows[i].lower_bound(j+1);  
  57.             if(right != rows[i].end()) cnt++,sum += a[i][*right];
  58.             auto left = rows[i].lower_bound(j); 
  59.             if(left != rows[i].begin()) cnt++,sum += a[i][*(--left)];
  60.             auto up = columns[j].lower_bound(i+1);
  61.             if(up != columns[j].end()) cnt++,sum += a[*up][j];
  62.             auto down = columns[j].lower_bound(i);
  63.             if(down != columns[j].begin()) cnt++,sum += a[*(--down)][j];
  64.  
  65.             if(cnt == 0) continue;
  66.             if(a[i][j]*cnt < sum) que.insert({i,j});
  67.         }
  68.     }
  69.  
  70.     while(sz(que) != 0){
  71.         set<pair<int,int>> new_que;
  72.  
  73.         for(auto x:que){
  74.             int i = x.f,j = x.s;
  75.             auto right = rows[i].lower_bound(j+1);  
  76.             if(right != rows[i].end()) new_que.insert({i,*right});
  77.             auto left = rows[i].lower_bound(j); 
  78.             if(left != rows[i].begin()) new_que.insert({i,*(--left)});
  79.             auto up = columns[j].lower_bound(i+1);
  80.             if(up != columns[j].end()) new_que.insert({*up,j});
  81.             auto down = columns[j].lower_bound(i);
  82.             if(down != columns[j].begin()) new_que.insert({*(--down),j});
  83.             skillsum -= a[i][j];
  84.             a[i][j] = 0; rows[i].erase(j); columns[j].erase(i);
  85.         }
  86.  
  87.         ans += skillsum;
  88.         que.clear();
  89.  
  90.         for(auto x:new_que){
  91.             int i = x.f,j = x.s;
  92.             if(a[i][j] == 0) continue;
  93.  
  94.             int cnt = 0,sum = 0;
  95.             auto right = rows[i].lower_bound(j+1);  
  96.             if(right != rows[i].end()) cnt++,sum += a[i][*right];
  97.             auto left = rows[i].lower_bound(j); 
  98.             if(left != rows[i].begin()) cnt++,sum += a[i][*(--left)];
  99.             auto up = columns[j].lower_bound(i+1);
  100.             if(up != columns[j].end()) cnt++,sum += a[*up][j];
  101.             auto down = columns[j].lower_bound(i);
  102.             if(down != columns[j].begin()) cnt++,sum += a[*(--down)][j];
  103.  
  104.             if(cnt == 0) continue;
  105.             if(a[i][j]*cnt < sum) que.insert({i,j});
  106.         }
  107.     }
  108.  
  109.     cout<<ans<<endl;
  110. }
  111.  
  112. signed main(){
  113.  
  114.    FastRead; 
  115.  
  116.     int t = 1; 
  117.     cin>>t;
  118.     FOR(i,1,t){
  119.         cout<<"Case #"<<i<<": ";
  120.         solve();
  121.     }
  122. }
  123.  
  124.  
  125.  
  126.  
Success #stdin #stdout 0s 4512KB
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/3qyGdY
language:
C++14 (gcc 8.3)
created:
4 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!