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

#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];

bool eaten[N];

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));
    int energy = 0;
    for (int i = 0; i < n; i++) {
      int lost = INF, idx = -1;
      for (int j = 0; j < n; j++) {
        int cur_lost = 0;
        if (eaten[j]) continue;
        for (int k = 0, s = si[j]; k < n; k++) {
          if (k == j || eaten[k]) continue;
          if (ei[k] <= s * li[k]) {
            cur_lost += ei[k];
          } else {
            cur_lost += s * li[k];
          }
        }
        if (cur_lost < lost || cur_lost == lost) {
          lost = cur_lost;
          idx = j;
        }
      }
      if (idx == -1) break;
      eaten[idx] = true;
      energy += ei[idx];
      for (int j = 0, s = si[idx]; j < n; j++) {
        if (eaten[j]) continue;
        if (ei[j] <= s * li[j]) eaten[j] = true;
        ei[j] -= s * li[j];
      }
    }
    printf("Case #%d: %d\n", t, energy);
  }
  return 0;
}