gistfile1.txt

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct Pair {
  int val;
  int idx;
  Pair() {}
  Pair(int val, int idx) : val(val), idx(idx) {}
  bool operator<(const Pair& other) const {
    return val < other.val;
  }
};

int main() {
  setvbuf(stdin, NULL, _IOFBF, 10000);
  setvbuf(stdout, NULL, _IOFBF, 10000);

  int orig[1024];
  int arr[1024];
  Pair pmat[130][130];
  //Pair mat[130][130];
  int kmat[1000];
  int mat[1000][1000];
  int n_cases;
  scanf("%d", &n_cases);
  for (int ctr = 0; ctr < n_cases; ++ctr) {
    if (ctr > 0) putchar('\n');
    memset(kmat, 0, sizeof(kmat));
    memset(mat, 0, sizeof(mat));
    
    int n;
    int t;
    int m;
    scanf("%d %d %d", &n, &t, &m);

    for (int i = 0; i < n-1; ++i) {
      scanf("%d,", &arr[i]);
    }
    scanf("%d", &arr[n-1]);
    memcpy(orig, arr, sizeof(arr));

    for (int i = n-1; i >= 0; --i) {
      // insertion sort
      int pivot = arr[i];
      int ins = i;
      while (ins < i-1 && arr[ins+1] < pivot) {
        arr[ins] = arr[ins+1];
        ++ins;
      }
      arr[ins] = pivot;

      int rem = t;
      for (int j = i; j < n; ++j) {
        if (rem >= arr[j]) {
          ++kmat[i];
          rem -= arr[j];
        } else break;
      }
    }


    memcpy(arr, orig, sizeof(orig));

    for (int i = 0; i < n; ++i) {
      printf("%d ", orig[i]);
    }
    puts("");
    for (int i = 0; i < n; ++i) {
      printf("%d ", arr[i]);
    }
    puts("");
    for (int i = 0; i < n; ++i) {
      // ins sort
      int pivot = arr[i];
      int ins = i;
      while (ins > 0 && arr[ins-1] > pivot) {
        arr[ins] = arr[ins-1];
        --ins;
      }
      arr[ins] = pivot;
      
      // fill
      int rem = t;
      for (int j = 0; j <= i; ++j) {
        if (rem >= arr[j]) {
          ++mat[1][i+1];
          rem -= arr[j];
        } else break;
      }
    }
    for (int i = 0; i < n; ++i) {
      printf("%d ", arr[i]);
    }
    puts("");

    for (int i = 2; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        for (int k = 0; k < j; ++k) {
          mat[i][j] = max(mat[i][j],
              mat[i-1][k] + arr[k]);
        }
      }
    }
    for (int i = 0; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        printf("%4d ", mat[i][j]);
      }
      printf("\n");
    }
    printf("%d\n", mat[m][n]);
  }
  
  return 0;
}