fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  7. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  8. #define nl "\n"
  9. #define pb emplace_back
  10. #define sz(s) (int)s.size()
  11.  
  12. typedef long long ll;
  13. typedef vector<int> vi;
  14.  
  15. int main(){
  16.     ios::sync_with_stdio(false);
  17.     cin.tie(nullptr);
  18.     int tt; if(!(cin>>tt)) return 0;
  19.     while(tt--){
  20.         int X,Y,Z; cin>>X>>Y>>Z;
  21.         vector<vector<vector<int>>> a(X, vector<vector<int>>(Y, vector<int>(Z,0)));
  22.         ff(x,0,X-1) ff(y,0,Y-1) ff(z,0,Z-1) cin>>a[x][y][z];
  23.  
  24.         // collect positions that are 1 and map to index
  25.         vector<int> posList; posList.reserve(X*Y*Z);
  26.         vector<int> lin2idx(X*Y*Z, -1);
  27.         int U = 0;
  28.         ff(x,0,X-1) ff(y,0,Y-1) ff(z,0,Z-1){
  29.             if(a[x][y][z]==1){
  30.                 int lin = (x*Y + y)*Z + z;
  31.                 lin2idx[lin] = U++;
  32.                 posList.pb(lin);
  33.             }
  34.         }
  35.         if(U==0){
  36.             cout<<0<<nl;
  37.             continue;
  38.         }
  39.  
  40.         // build 3D prefix sum (1-based)
  41.         vector<vector<vector<int>>> pref(X+1, vector<vector<int>>(Y+1, vector<int>(Z+1,0)));
  42.         for(int x=1;x<=X;x++) for(int y=1;y<=Y;y++) for(int z=1;z<=Z;z++){
  43.             pref[x][y][z] = a[x-1][y-1][z-1]
  44.                 + pref[x-1][y][z] + pref[x][y-1][z] + pref[x][y][z-1]
  45.                 - pref[x-1][y-1][z] - pref[x-1][y][z-1] - pref[x][y-1][z-1]
  46.                 + pref[x-1][y-1][z-1];
  47.         }
  48.         auto sum_box = [&](int x1,int x2,int y1,int y2,int z1,int z2)->int{
  49.             // inputs 1-based inclusive
  50.             int s = pref[x2][y2][z2]
  51.                 - pref[x1-1][y2][z2] - pref[x2][y1-1][z2] - pref[x2][y2][z1-1]
  52.                 + pref[x1-1][y1-1][z2] + pref[x1-1][y2][z1-1] + pref[x2][y1-1][z1-1]
  53.                 - pref[x1-1][y1-1][z1-1];
  54.             return s;
  55.         };
  56.  
  57.         // enumerate all boxes that are fully 1
  58.         struct Box { int cost; vector<int> elems; };
  59.         vector<Box> boxes;
  60.         boxes.reserve(10000);
  61.  
  62.         // enumerate all boxes: complexity ok since X*Y*Z <= 5000
  63.         for(int x1=1;x1<=X;x1++){
  64.             for(int x2=x1;x2<=X;x2++){
  65.                 for(int y1=1;y1<=Y;y1++){
  66.                     for(int y2=y1;y2<=Y;y2++){
  67.                         for(int z1=1;z1<=Z;z1++){
  68.                             for(int z2=z1;z2<=Z;z2++){
  69.                                 int vol = (x2-x1+1)*(y2-y1+1)*(z2-z1+1);
  70.                                 int s = sum_box(x1,x2,y1,y2,z1,z2);
  71.                                 if(s==vol && vol>0){
  72.                                     Box B;
  73.                                     B.cost = min({x2-x1+1, y2-y1+1, z2-z1+1});
  74.                                     B.elems.reserve(vol);
  75.                                     for(int x=x1-1;x<=x2-1;x++){
  76.                                         for(int y=y1-1;y<=y2-1;y++){
  77.                                             for(int z=z1-1;z<=z2-1;z++){
  78.                                                 int lin = (x*Y + y)*Z + z;
  79.                                                 int idx = lin2idx[lin];
  80.                                                 if(idx!=-1) B.elems.pb(idx);
  81.                                             }
  82.                                         }
  83.                                     }
  84.                                     if(!B.elems.empty()) boxes.pb(move(B));
  85.                                     // small safeguard: avoid explosion
  86.                                     if((int)boxes.size() > 200000) break;
  87.                                 }
  88.                             }
  89.                             if((int)boxes.size() > 200000) break;
  90.                         }
  91.                         if((int)boxes.size() > 200000) break;
  92.                     }
  93.                     if((int)boxes.size() > 200000) break;
  94.                 }
  95.                 if((int)boxes.size() > 200000) break;
  96.             }
  97.             if((int)boxes.size() > 200000) break;
  98.         }
  99.  
  100.         // If boxes exploded, fallback: use singletons (each 1×1×1)
  101.         if(boxes.empty()){
  102.             // fall back: each single 1-cell as a box (cost=1)
  103.             for(int i=0;i<U;i++){
  104.                 Box B; B.cost = 1; B.elems = {i};
  105.                 boxes.pb(move(B));
  106.             }
  107.         } else if((int)boxes.size() > 200000){
  108.             boxes.clear();
  109.             for(int i=0;i<U;i++){
  110.                 Box B; B.cost = 1; B.elems = {i};
  111.                 boxes.pb(move(B));
  112.             }
  113.         }
  114.  
  115.         int M = boxes.size();
  116.         // covered flag
  117.         vector<char> covered(U, 0);
  118.         int remain = U;
  119.         int totalCost = 0;
  120.  
  121.         // Precompute for speed: each box's elems vector and cost already
  122.         // Greedy loop: pick box with max (newly_covered / cost)
  123.         while(remain > 0){
  124.             double bestVal = -1.0;
  125.             int bestIdx = -1;
  126.             int bestNew = 0;
  127.             for(int i=0;i<M;i++){
  128.                 int newly = 0;
  129.                 for(int e : boxes[i].elems) if(!covered[e]) ++newly;
  130.                 if(newly==0) continue;
  131.                 double val = double(newly) / double(boxes[i].cost);
  132.                 if(val > bestVal + 1e-12){
  133.                     bestVal = val;
  134.                     bestIdx = i;
  135.                     bestNew = newly;
  136.                 }
  137.             }
  138.             if(bestIdx==-1){
  139.                 // something wrong -> cover remaining by singletons
  140.                 totalCost += remain;
  141.                 break;
  142.             }
  143.             totalCost += boxes[bestIdx].cost;
  144.             for(int e : boxes[bestIdx].elems){
  145.                 if(!covered[e]) { covered[e]=1; --remain; }
  146.             }
  147.         }
  148.  
  149.         cout<<totalCost<<nl;
  150.     }
  151.     return 0;
  152. }
  153.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
1
4 4 4
1 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 1 1
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
stdout 
6
https://ideone.com/cpA3Yi
language:
C++14 (gcc 8.3)
created:
9 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!