fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17. #define MAX 10004
  18.  
  19. int n;
  20. struct Stone
  21. {
  22.     int len,wid,hei,id;
  23. };
  24. vector<Stone> stones;
  25.  
  26. bool cmp(const Stone &x, const Stone &y)
  27. {
  28.     return x.len>y.len || x.len==y.len && x.wid>y.wid;
  29. }
  30.  
  31. int trace[2*MAX],f[2*MAX];
  32. void calc()
  33. {
  34.     memset(trace,-1,sizeof(trace));
  35.     int ans=0,idx=-1;
  36.     foru(i,0,stones.size()-1)
  37.     {
  38.         f[i]=stones[i].hei;
  39.         foru(j,0,i-1)
  40.         {
  41.             if(stones[j].len>=stones[i].len && stones[j].wid>=stones[i].wid)
  42.             {
  43.                 if(f[i]<f[j]+stones[i].hei)
  44.                 {
  45.                     f[i]=f[j]+stones[i].hei;
  46.                     trace[i]=j;
  47.                 }
  48.             }
  49.         }
  50.         if(ans<f[i])
  51.         {
  52.             ans=f[i];
  53.             idx=i;
  54.         }
  55.     }
  56.     cout<<ans<<el;
  57.     vector<Stone> v;
  58.     while(idx!=-1)
  59.     {
  60.         v.pb(stones[idx]);
  61.         idx=trace[idx];
  62.     }
  63.     cout<<(int)v.size()<<el;
  64.     bool change=false;
  65.     ford(i,v.size()-1,0)
  66.     {
  67.         cout<<v[i].id<<' '<<min(v[i].wid,v[i].len)<<' '<<max(v[i].wid,v[i].len)<<' '<<v[i].hei<<el;
  68.     }
  69. }
  70.  
  71. int main()
  72. {
  73.     fastio
  74.     #ifndef ONLINE_JUDGE
  75.     freopen(FILE ".inp","r",stdin);
  76.     freopen(FILE ".out","w",stdout);
  77.     #endif // ONLINE_JUDGE
  78.  
  79.     cin>>n;
  80.     foru(i,1,n)
  81.     {
  82.         int a,b,c; cin>>a>>b>>c;
  83.         if(a<=b && a<=c) swap(a,c); // a=min(a,b,c)
  84.         if(b<=a && b<=c) swap(b,c); // b=min(a,b,c)
  85.         stones.pb({a,b,c,i}); 
  86.         if(a!=b) stones.pb({b,a,c,i});
  87.     }
  88.     sort(stones.begin(),stones.end(),cmp);
  89.     calc();
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/BOf2ZP
language:
C++14 (gcc 8.3)
created:
2 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!