Go: package main

import (
	"bufio"
	"os"
	"strings"
	"strconv"
	"fmt"
	)

var scanner = bufio.NewScanner(os.Stdin)
const MAX_WIDTH = 1500000

func main() {
	// 二分探索で探す
	// 二分探索はソート済みの配列に対して、特定の条件を満たす値を
	// 効率よく選択するアルゴリズム
	for scanner.Scan() {
		buf := strings.Split(scanner.Text(), " ")
		m, _ := strconv.Atoi(buf[0])
		n, _ := strconv.Atoi(buf[1])
		if n == 0 && m == 0 {
			break
		}
		books := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			books[i], _ = strconv.Atoi(scanner.Text())
		}
		check := func(width int) bool {
			// widthの幅の本棚に順番にbooksを詰めて行ったら
			// 何段になるのかを確認し、それがmを以下であることを確認する
			shelf_index := 1
			position_in_stage := 0
			for i := 0; i < n; i++ {
				// 入れることができない本がある時点でこのwidthは不採用
				if books[i] > width {
					return false
				}
				// 新たに本を追加することができるかをチェックする
				if position_in_stage + books[i] <= width {
					// 新たに本を入れることができたので、そのステージにおける
					// 現在の本の位置を記録
					position_in_stage += books[i]
				} else {
					// 新たな本を入れることができなかったので、一段下のステージに
					// 入れれば良い
					position_in_stage = books[i]
					shelf_index++ // 本棚のステージ数が増えた
				}
			}
			return shelf_index <= m // 条件を満たすかの確認
		}
		low, high := 0, MAX_WIDTH
		for low < high {
			mid := (low+high)/2
			if check(mid) {
				high = mid
			} else {
				low = mid+1
			}
			// log.Printf("low: %d, high: %d\n", low, high)
		}
		fmt.Println(low)
	}
}

C++: #include <bits/stdc++.h>
using namespace std;

int main() {
  for(int m, n; cin >> m >> n && (m|n);) {
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    int l = *min_element(a.begin(), a.end()) , r = 1500001;
    while(r-l) {
      int mid = (l+r)/2;
      int x = 0, y = 1;
      for(int i = 0; i < n; ++i) {
        if(x + a[i] > mid) {
          x = a[i];
          ++y;
        } else {
          x += a[i];
        }
      }
      if(y <= m) {
        r = mid;
      } else {
        l = mid+1;
      }
    }
    cout << r << endl;
  }
  return 0;
}

C++: #include<iostream>

using namespace std;

int main(){
	int n,m;
	while(1){
		cin>>n>>m;
		if(n==0 && m==0){
			break;
		}
		int hon[150];
		for(int i=0;i<m;i++){
			cin>>hon[i];
		}
		
		int right,left;
		right=left=0;
		
		for(int i=0;i<m;i++){
			left+=hon[i];
		}
		
		while(1){
			double h=(double)(left+right)/2;
			//printf("%d %d %lf\n",right,left,h);
			
			int ans=0;
			
			int now=0;
			int dan=1;
			for(int i=0;i<m;i++){
				if(now+hon[i]>h){
					if(now==0){
						dan=100000;
						break;
					}
					now=0;
					dan++;
					i--;
					continue;
				}
				now+=hon[i];
			}
			
			//printf("%lf zi dan = %d\n",h,dan);
			
			if(dan<=n){
				ans=1;
			}
			if(ans==1){
				left=h+0.499;
			}else{
				right=h;
			}
			if((int)left==(int)right+1){
				printf("%d\n",left);
				break;
			}
		}
	}
}

C++: 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
  int m,n;
  int low,high,medi;
  int column,breadth;
  int i;
  bool f;
  while(cin>>m>>n,m,n){
    vector<int>v(n);
    for(i=low=0;i<n;i++){cin>>v[i];low+=v[i];}
    low/=m;
    high=1500000;
    while(1){
      medi=(low+high)/2;
      if(medi==low||medi==high)break;
      breadth=column=f=0;
      for(i=0;i<n;i++){
	if(medi<v[i]){f=1;break;}
	if(breadth+v[i]<=medi){
	  breadth+=v[i];
	}else{
	  breadth=v[i];
	  column++;
	  if(column==m){f=1;break;}
	}
      }
      if(f)low=medi;
      else high=medi;
    }
    cout<<high<<endl;
  }
}

C++: #include <iostream>

using namespace std;

#define BOOK_NUM_MAX 100
#define SHELF_NUM_MAX 20

int book_thick[BOOK_NUM_MAX] = {0};
int dp_table[SHELF_NUM_MAX][BOOK_NUM_MAX] = {-1};

int solve(int m, int n){
	int sum, val, min, tmp;
	
	if(dp_table[m][n] == -1){
		if(m == 1){
			sum = 0;
			for(int i=1; i <= n;++i){
				sum += book_thick[n - i];
			}
			val = sum;
		}else if(n == 0){
			val = 0;
		}else{
			sum = 0;
			min = solve(m-1, n);
			for(int i=1; i <= n;++i){
				sum += book_thick[n - i];
				tmp = solve(m-1,n-i);
				tmp = sum > tmp ? sum : tmp;
				min = min > tmp ? tmp : min; 
			}
			val = min;
		}
		dp_table[m][n] = val;
	}else{
		val = dp_table[m][n];
	}
	return val;
}

int main() {
	
	int m, n;
	int i,j;
	
	while(cin >> m >> n, m!= 0 && n!= 0){
		for(i=0;i<n;++i){
			cin >> book_thick[i];
		}
		
		for(int i=0;i<SHELF_NUM_MAX;++i){
			for(int j=0;j<BOOK_NUM_MAX;++j){
				dp_table[i][j] = -1;
			}
		}
		
		cout << solve(m,n) << endl;
	}
	
	return 0;
}

C++: #include <iostream>

using namespace std;

typedef unsigned long long ull;

int m, n;
ull w[100];

bool b(ull W)
{
	int need = 1;
	ull s = 0;
	for(int i=0; i<n; i++)
	{
		if(w[i] > W)
		{
			return false;
		}

		if(s+w[i] > W)
		{
			need++;
			s = 0;
		}
		s+=w[i];
	}
	return need <= m;
}

int main()
{
	while( 1 )
	{
		scanf("%d", &m);
		scanf("%d", &n);
		if((m|n)==0) break;
		
		for(int i=0; i<n; i++)
		{
			scanf("%llu", &w[i]);
		}
		
		ull l = 1;
		ull r = 1500000;
		while(r-l > 1)
		{
			ull mid = (r + l) / 2;
			if(b(mid)) r = mid;
			else l = mid;
		}

		printf("%llu\n", b(l)?l:r);
	}
}

C++: #include <iostream>
#include <algorithm>
#include <numeric>

#include <string.h>

#define INT_INF 2000000

int m, n;

int a[100 + 1];

int memo[20 + 1][100 + 1];

int search(int i, int j)
{
  if (memo[i][j] >= 0)
    return memo[i][j];

  if (i == 1)
    return memo[i][j] = std::accumulate(a + j, a + n, 0);

  int am = INT_INF;
  
  for (int k = j, s = 0; k < n; s += a[k], k ++)
    am = std::min(std::max(search(i - 1, k), s),
			   am);

  return memo[i][j] = am;
}

int main(int argc, char** argv)
{
  while (1) {
    std::cin >> m >> n;
    
    if (m == 0)
      break;

    for (int i = 0; i < n; i ++)
      std::cin >> a[i];

    memset(memo, -1, sizeof(memo));

    std::cout << search(m, 0) << std::endl;
  }
}

C++: #include <stdio.h>
#include <math.h>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) cerr << #x << "=" << static_cast<bitset<16> >(x) << endl;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 10000000;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
using namespace std;
typedef pair<int, int> P;

/** Problem0181 : Persistence **/
int M, N;
int W[100];

bool check(int w)
{
	int cw=0, cm=1;
	rep(i, N) {
		if (W[i]>w) return false;
		
		if (cw+W[i]>w) {
			cm++;
			cw=0;
		}
		cw+=W[i];
	}
		
	return cm<=M;
}

int main()
{
	while (cin>>M>>N, M||N) {
		rep(i, N) {
			cin>>W[i];
		}
		
		int l=0, u=1500000;
		while (u-l>1) {
			int mid = (l+u)/2;
			if (check(mid)) {
				u=mid;
			} else {
				l=mid;
			}
		}
		
		cout << u << endl;
	}
}

C++: #include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;

int m, n;
int w[MAX];

bool c(int x) {
    bool used[n];
    fill(used, used + n, false);
    for (int i = 0; i < m; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            if (used[j]) continue;
            if (sum + w[j] <= x) {
                sum += w[j];
                used[j] = true;
            } else {
                break;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) return false;
    }
    return true;
}

int main() {
    while (true) {
        cin >> m >> n;
        if (m == 0 && n == 0) return 0;
        for (int i = 0; i < n; i++) {
            cin >> w[i];
        }
        
        int l = 0, r = 1500001;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (c(mid)) r = mid;
            else l = mid;
        }
        cout << r << endl;
    }
}