fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<ll, ll>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. struct Item
  12. {
  13.     ll x, y, h;
  14.     int id;
  15.  
  16.     Item(ll x = 0, ll y = 0, ll h = 0, int id = 0) :
  17.         x(x), y(y), h(h), id(id) {};
  18.     bool operator < (const Item &other) const
  19.     {
  20.         return x > other.x;
  21.     }
  22. };
  23.  
  24. const int maxn = 3e3;
  25. const ll INF = 1e18;
  26.  
  27. int n;
  28. vector<Item> it, trace;
  29. ii dp[maxn + 10], ans;
  30.  
  31. int main()
  32. {
  33.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  34.     if (fopen("TOWER.INP", "r"))
  35.     {
  36.         freopen("TOWER.INP", "r", stdin);
  37.         freopen("TOWER.OUT", "w", stdout);
  38.     }
  39.  
  40.     cin >> n;
  41.     for (int i = 1; i <= n; i++)
  42.     {
  43.         ll x, y, z;
  44.         cin >> x >> y >> z;
  45.         it.push_back(Item(x, y, z, i));
  46.         it.push_back(Item(z, x, y, i));
  47.         it.push_back(Item(y, z, x, i));
  48.     }
  49.     n = it.size();
  50.     it.push_back(Item(INF, INF, 0, 0));
  51.     sort(it.begin(), it.end());
  52.     for (int i = 1; i <= n; i++)
  53.         for (int j = 0; j < i; j++)
  54.             if (it[j].id != it[i].id && it[j].x > it[i].x && it[j].y > it[i].y)
  55.                 dp[i] = max(dp[i], {dp[j].fi + it[i].h, j});
  56.     for (int i = 1; i <= n; i++)
  57.         if (ans.fi < dp[i].fi)
  58.             ans = {dp[i].fi, i};
  59.     while (ans.se)
  60.     {
  61.         trace.push_back(it[ans.se]);
  62.         ans.se = dp[ans.se].se;
  63.     }
  64.     reverse(trace.begin(), trace.end());
  65.     cout << ans.fi << ' ' << trace.size(), el;
  66.     for (Item res : trace)
  67.     {
  68.         ll x = res.x;
  69.         ll y = res.y;
  70.         if (x < y)
  71.             swap(x, y);
  72.         cout << x << ' ' << y << ' ' << res.h, el;
  73.     }
  74. }
  75.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/4I0Ol3
language:
C++14 (gcc 8.3)
created:
15 hours 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!