fork download
copy 
  1. //VTBABY - Vườn treo Babylon
  2. //https://l...content-available-to-author-only...e.net/problem/vtbaby
  3. #include <bits/stdc++.h>
  4. #define ll long long
  5. #define maxn 100006
  6. using namespace std;
  7.  
  8. int n, F[maxn], before[maxn];
  9. vector<int> X(3, 0), used(3, 0);
  10. //0: cao; 1: dai; 2: rong
  11. vector<vector<int>> CauHinh;
  12. struct stone{
  13.     int d, r, c, id;
  14. } A[maxn];
  15.  
  16. bool cmp(stone A, stone B){
  17.     return A.d*A.r*A.c>=B.d*B.r*B.c;
  18. }
  19.  
  20. stone change(int x, int y, int z, int id, vector<int> V){
  21.     vector<int> v;
  22.     v.push_back(x);
  23.     v.push_back(y);
  24.     v.push_back(z);
  25.     sort(v.begin(), v.end(), greater<int>());
  26.     stone tmp;
  27.     for (int i=0; i<=2; i++){
  28.         if (V[i]==0) tmp.c=v[i];
  29.         else if (V[i]==1) tmp.d=v[i];
  30.         else if (V[i]==2) tmp.r=v[i];
  31.     }
  32.     tmp.id=id;
  33.     return tmp;
  34. }
  35.  
  36. void Try(int i){
  37.     for (int j=0; j<=2; j++){
  38.         if (used[j]==1) continue;
  39.         X[i]=j;
  40.         used[j]=1;
  41.         if (i==2) CauHinh.push_back(X);
  42.         else Try(i+1);
  43.         used[j]=0;
  44.     }
  45. }
  46.  
  47. int dp(int k){
  48.     cout<< k<< endl;
  49.     for (int i=1; i<=n; i++){
  50.         A[i]=change(A[i].d, A[i].r, A[i].c, A[i].id, CauHinh[k]);
  51.         cout<< i<< " "<< A[i].d<< " "<< A[i].r<< " "<< A[i].c<< endl;
  52.     }
  53.     int idmax=0;
  54.     memset(F, 0, sizeof F);
  55.     memset(before, 0, sizeof before);
  56.     for (int i=1; i<=n; i++){
  57.         F[i]=A[i].c;
  58.         for (int j=0; j<i; j++){
  59.             if (A[i].d<=A[j].d && A[i].r<=A[j].r && F[j]+A[i].c>F[i]){
  60.                 F[i]=F[j]+A[i].c;
  61.                 before[i]=j;
  62.             }
  63.         }
  64.         if (F[i]>F[idmax]) idmax=i;
  65.     }
  66.     int tmp=idmax;
  67.     cout<< F[idmax]<< endl;
  68.     stack<int> st;
  69.     while (tmp!=0){
  70.         st.push(tmp);
  71.         tmp=before[tmp];
  72.     }
  73.     while (!st.empty()){
  74.         cout<< st.top()<< " ";
  75.         st.pop();
  76.     }
  77.     cout<< endl;
  78.     return F[idmax];
  79. }
  80.  
  81. int main(){
  82.     ios_base::sync_with_stdio(false);
  83.     cin.tie(nullptr); cout.tie(nullptr);
  84.     cin>> n;
  85.     Try(0);
  86.     for (int i=1; i<=n; i++){
  87.         int x, y, z; cin>> x>> y>> z;
  88.         A[i]={x, y, z, i};
  89.     }
  90.     A[0]={0, 0, 0, 0};
  91.     sort(A+1, A+n+1, cmp);
  92.     int ma=0;
  93.     for (int i=0; i<6; i++) ma=max(ma, dp(i));
  94.     cout<< ma<< endl;
  95.     for (int i=0; i<6; i++){
  96.         for (int x:CauHinh[i]) cout<< x<< " ";
  97.         cout<< endl;
  98.     }
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
stdout
copy 
0
1 64 62 84
2 93 23 97
3 53 26 58
4 41 31 59
5 33 27 83
226
1 4 5 
1
1 62 64 84
2 23 93 97
3 26 53 58
4 31 41 59
5 27 33 83
226
1 4 5 
2
1 84 62 64
2 97 23 93
3 58 26 53
4 59 31 41
5 83 27 33
117
1 3 
3
1 84 64 62
2 97 93 23
3 58 53 26
4 59 41 31
5 83 33 27
93
1 4 
4
1 62 84 64
2 23 97 93
3 26 58 53
4 31 59 41
5 27 83 33
117
1 3 
5
1 64 84 62
2 93 97 23
3 53 58 26
4 41 59 31
5 33 83 27
93
1 4 
226
0 1 2 
0 2 1 
1 0 2 
1 2 0 
2 0 1 
2 1 0
https://ideone.com/I52Gxc
language:
C++14 (gcc 8.3)
created:
35 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!