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;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef complex<double> Point;
typedef long long ll;
const int INF = 114514810;
const int MOD = 1000000007;
const double EPS = 1e-10;
const double PI = acos(-1.0);
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

int m, n;
int book[105];

bool check(int bre)
{
	int cnt = 0;
	int tmp = 0;
	REP(i, n)
	{
		if (cnt > m || book[i]>bre) return false;
		if (tmp + book[i] > bre)
		{
			cnt++;
			tmp = book[i];
		}
		else
		{
			tmp += book[i];
		}
	}
	return cnt < m;
}

int main()
{
	while (cin >> m >> n, m)
	{
		REP(i, n) cin >> book[i];
		int lb = 0; int ub = 2000000;
		while (ub - lb > 1)
		{
			int mid = (ub + lb) / 2;
			if (check(mid)) ub = mid;
			else lb = mid;
		}
		cout << ub << endl;
	}
	return 0;
}

C++: #include <stdio.h>
int m, n, a[100];
bool check(int x) {
	int pos = 0, r = 0;
	for(int i = 0; i < m; i++) {
		while(pos != n && r + a[pos] <= x) r += a[pos++];
		if(pos == n) return true; r = 0;
	}
	return false;
}
int main() {
	while(scanf("%d%d", &m, &n), n) {
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
		int l = 0, r = 1500001;
		while(r - l > 1) {
			int m = (l + r) / 2;
			if(check(m)) r = m;
			else l = m;
		}
		printf("%d\n", r);
	}
}

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

#define int long long
#define DEBUG 0
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using pii = pair<int, int>; using vi = vector<int>;
static const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
static const int MOD = (int)(1e9 + 7);

int m, n;
//??¬?£?????????????????????????
bool f(vector<int> &w, int a) {
	int cnt = 1;
	int tmp = 0;
	for (int i = 0; i < w.size(); i++) {
		if (tmp + w[i] > a) {
			if (tmp == 0)return false;
			cnt += 1;
			tmp = 0;
		}
		tmp += w[i];
	}
	if (cnt > m)return false;
	return true;
}

signed main() {
	for (; cin >> m >> n&&m;) {
		vector<int> w(n);
		rep(i, 0, n)cin >> w[i];

		int L = 0, R = 1500001;
		rep(i,0,22){
			int MID = (L + R) / 2;
			if (f(w, MID))R = MID;
			else L = MID;
		}
		cout << R << endl;
	}
	return 0;
}

C++: #include <iostream>
using namespace std;

const int BOOK_LIMIT = 100;
const int COL_LIMIT = 20;
const int WIDTH_LIMIT = 1500000;

struct Column
{
	int head;
	int w;
};

class Shelf
{
public:
	void input( int numColumn, int numBook )
	{
		width = 0;
		m = numColumn;
		n = numBook;
		int sum = 0;
		int w = 0;
		for( int i = 0; i < n; ++i ){
			int t;
			cin >> t;
			book[ i ] = t;
			sum += t;
			if( sum > WIDTH_LIMIT ){
				sum = WIDTH_LIMIT;
			}
			if( w < t ){
				w = t;
			}
		}
		width = ( sum / n > w ? sum / n : w );
	}

	int putAll()
	{
		int ib = putInit();
		int low = m - 1;
		while( ib < n ){
			if( col[ low ].w + book[ ib ] > width ){
				secureSpace( ib );
			}
			if( col[ low ].w == 0 ){
				col[ low ].head = ib;
			}
			col[ m - 1 ].w += book[ ib++ ];
		}
		return width;
	}

	int putInit()
	{
		int ib = 0;
		int is = 0;
		while( ib < n && is < m ){
			col[ is ].head = ib;
			col[ is ].w = 0;
			while( col[ is ].w + book[ ib ] <= width ){
				col[ is ].w += book[ ib ];
				++ib;
			}
			++is;
		}
		while( is < m ){
			col[ is ].head = -1;
			col[ is ].w = 0;
			++is;
		}
		return ib;
	}

	void secureSpace( int ib )
	{
		int ex = 0x7fffffff;
		int is = 0;
		for( int i = 0; i < m - 1; ++i ){
			int e = book[ col[ i + 1 ].head ] - ( width - col[ i ].w );
			if( e < ex ){
				ex = e;
				is = i + 1;
			}
		}
		width += ex;
		for( int i = is; i < m; ++i ){
			raiseBook( i );
		}
		if( col[ m - 1 ].w + book[ ib ] > width ){
			secureSpace( ib );
		}
	}

	void raiseBook( int is )
	{
		int upper = is - 1;
		int lower = is;
		int bw = book[ col[ lower ].head ];
		if( ( bw + col[ upper ].w ) <= width ){
			if( col[ upper ].w == 0 ){
				col[ upper ].head = col[ lower ].head;
			}
			col[ upper ].w += bw;
			++col[ lower ].head;
			col[ lower ].w -= bw;
			if( col[ lower ].w == 0 ){
				col[ lower ].head = -1;
			}
		}
	}

private:
	int book[ BOOK_LIMIT ];
	Column col[ COL_LIMIT ];
	int m, n;
	int width;
};

int main()
{
	int m, n;
	while( cin >> m >> n && ( m || n ) ){
		Shelf s;
		s.input( m, n );
		cout << s.putAll() << endl;
	}

	return 0;
}

C++: #include <iostream>
using namespace std;

bool check(int* books, int width, int m,int n);

int main(void){
  int m,n;
  while(1){
    cin>>m>>n;
    if(m==0 and n==0)break;
    int books[n];
    for(int i=0;i<n;i++){
      cin>>books[i];
    }
    int min=0;
    int max=1500000;
    int mid;
    while(max-min>5){
      mid=(min+max)/2;
      if(check(books,mid,m,n)){
        max=mid;
      }
      else{
        min=mid;
      }
    }
    int retval;
    for(int i=max;i>=min;i--){
      if(check(books,i,m,n)){
        retval=i;
      }
    }
    cout<<retval<<endl;
  }
  return 0;
}


bool check(int* books, int width, int m, int n){
  int row=1;
  int w=0;
  for(int i=0;i<n;i++){
    if(books[i]>width)return false;
    if(w+books[i]<=width){
      w+=books[i];
    }
    else{
      row+=1;
      w=books[i];
    }
  }
  return row<=m;
}