leetcode-go/written-exam/kickstart-2019-B/no2/main.cc

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100;
const int INF = 1 << 30;

int n, si[N], ei[N], li[N];
int energy;

bool eaten[N];

int energy_left(int sec, int e) {
  int left = 0;
  for (int i = 0; i < n; i++) {
    if (eaten[i]) continue;
    if (li[i] * sec < ei[i]) left += ei[i] - li[i] * sec;
  }
  return left;
}

void dfs(int i, int sec, int e) {
  int left = energy_left(sec, e);
  if (left + e < energy) return;
  eaten[i] = true;
  if (li[i] * sec < ei[i]) {
    e += ei[i] - li[i] * sec;
    energy = max(energy, e);
  }
  for (int j = 0; j < n; j++) {
    if (eaten[j]) continue;
    dfs(j, sec + si[i], e);
  }
  eaten[i] = false;
}

int main() {
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d %d", &si[i], &ei[i], &li[i]);
    memset(eaten, 0, sizeof(eaten));
    energy = 0;
    for (int i = 0; i < n; i++) dfs(i, 0, 0);
    printf("Case #%d: %d\n", t, energy);
  }
  return 0;
}