fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Tower of Babylon
  4. //
  5. //  Created by Himanshu on 17/09/21.
  6. //
  7.  
  8. #include<cstdio>
  9. #include<iostream>
  10. #include<algorithm>
  11.  
  12. using namespace std;
  13.  
  14. struct block {
  15.  int x,y,z;
  16. };
  17.  
  18. bool cmp(const struct block &a,const struct block &b) {
  19.     if(a.x != b.x)
  20.         return (a.x < b.x);
  21.     else if(a.y != b.y)
  22.         return (a.y < b.y);
  23.     else
  24.         return (a.z < b.z);
  25. }
  26.  
  27. block newBlock(int p,int q,int r) {
  28.     block b;
  29.     b.x = p;
  30.     b.y = q;
  31.     b.z = r;
  32.     return b;
  33. }
  34.  
  35. int main() {
  36.     int n, ans, p, q, r;
  37.     scanf("%d",&n);
  38.  
  39.     // Since each block can be rotated in 6 ways, 1 for each face
  40.     int N = 6*n;
  41.     block b[N];
  42.     int lis[N];
  43.  
  44.     // Input terminates for n = 0, according to problem statement
  45.     while(n != 0) {
  46.         int j = 0;
  47.         ans = 0;
  48.  
  49.         for(int i=0; i<n; i++) {
  50.             scanf("%d %d %d",&p,&q,&r);
  51.  
  52.             // Adding all the combinations obtained by rotating a cuboid
  53.             b[j++] = newBlock(p,q,r);
  54.             b[j++] = newBlock(q,r,p);
  55.             b[j++] = newBlock(r,p,q);
  56.             b[j++] = newBlock(q,p,r);
  57.             b[j++] = newBlock(r,q,p);
  58.             b[j++] = newBlock(p,r,q);
  59.  
  60.         }
  61.         sort(b,b+N,&cmp);
  62.  
  63.         for(int i=0;i<N;i++) {
  64.             lis[i] = b[i].z;
  65.             for(j=0;j<i;j++) {
  66.  
  67.                 // To check if jth block can be placed above ith block
  68.                 if((b[j].x < b[i].x && b[j].y < b[i].y) || (b[j].x < b[i].y && b[j].y < b[i].x)) {
  69.                     //Optimal solution by including b[i] or not
  70.                     lis[i] = max(lis[i],(lis[j]+b[i].z));
  71.                 }
  72.             }
  73.             ans = max(ans,lis[i]);
  74.         }
  75.  
  76.         printf("%d\n",ans);
  77.         scanf("%d",&n);
  78.  }
  79.  
  80.  return 0;
  81. }
  82.  
Success #stdin #stdout 0s 5572KB
comments (?)
stdin
copy 
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0
stdout
copy 
342
https://ideone.com/PIY9HR
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!