[AtCoder] X - Tower

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : X - Tower
Source            : AtCoder Educational DP Contest
Category          : Dynamic Programing
Algorithm         : Exchange Arguments Technique
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll          long long int
 
static const int maxn = 1000 + 5;
 
struct structure
{
      ll w, s, v;
      structure(ll w = 0, ll s = 0, ll v = 0) : w(w), s(s), v(v) {}
      inline void read()
      {
            scanf("%lld %lld %lld", &w, &s, &v);
      }
      inline bool operator < (const structure &p) const
      {
            return ((p.w + p.s) > (w + s));
      }
};
 
int N;
structure block[maxn];
 
ll dp[1000+5][100000+4];
bool memoize[1000+5][100000+4];
 
inline ll solve(int pos, ll weight)
{
      if (pos > N) return 0;
      if (weight > 10000) return 0;
      ll &ret = dp[pos][weight];
      bool &mem = memoize[pos][weight];
      if (mem) return ret;
      mem = 1;
      ret = 0;
      if (weight <= block[pos].s)
      {
            ret = max(ret, block[pos].v + solve(pos+1, weight + block[pos].w));
      }
      ret = max(ret, solve(pos+1, weight));
      return ret;
}
 
int main()
{
      scanf("%d", &N);
      for (int i = 1; i <= N; i++) block[i].read();
      sort(block+1, block+N+1);
      printf("%lld", solve(1, 0));
}