gistfile1.cpp

#include<cstdio>
#include<vector>
#define INF 2000000000
#define MAX 10001000
using namespace std;

int Z, n, k, max_piece, sum_of_pieces, result;
int pieces[MAX];

void load_data();
void cleaning();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
  scanf("%d", &Z);
  while(Z--) {
    load_data();
    cleaning();
    calculate();
    print_data();
  }
  return 0;
}

void load_data() {
  int tmp;
  max_piece = 0; sum_of_pieces = 0;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &tmp);
    max_piece = max(max_piece, tmp);
    sum_of_pieces += tmp;
    pieces[i] = tmp;
  }
}

void cleaning() {

}

bool is_valid(int capacity) {
  int sum = 0; int i = 0; int tmp_k = 1;

  while (tmp_k <= k) {
    if (sum + pieces[i] <= capacity) sum += pieces[i++];
    else { tmp_k++; sum = 0; }
    if(i == n) return true;
  }
  return false;
}

void calculate() {
  //for (int i = max_piece; i <= sum_of_pieces; i++) {
    //if(is_valid(i)) printf("c: %d: tak\n", i);
    //else printf("c: %d: nie\n", i);
  //}

  int p, q, s;
  p = max_piece; q = sum_of_pieces;
  while (p<q) { 
    s = (p+q)/2; 
    if(is_valid(s)) { q = s; } 
    else { p = s+1; } 
  }
  result = p;
}

void print_data() {
  printf("%d\n", result);
}