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<iostream>
using namespace std;
int n, m;
int a[101];
bool search(int v);
int main()
{	
	while (true){
		cin >> m >> n;
		if (m == 0 && n == 0)break;
		for (int i = 0; i < n; i++){
			cin >> a[i];
		}
		int l, r;
		l = 0; r = 1 << 20;
		for (int i = 0; i < 100; i++){
			int mi = (l + r) / 2;
			if (search(mi))r = mi;
			else l = mi;
		}
		cout << r << endl;
	}
}
bool search(int v){
	int n2=0, m2=0,b=0;
	while (n2 < n&&m2 < m){
		if (b + a[n2] <= v){
			b += a[n2];
			n2++;
		}
		else{
			b = 0;
			m2++;
		}
	}
	if (n2 == n&&m2 < m)return true;
	return false;
}

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 / m > w ? sum / m : 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 && e + width > WIDTH_LIMIT ){
				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>
#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 s = 0; j < n; s += a[j], j ++)
    am = std::min(std::max(search(i - 1, j), 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 <iostream>
using namespace std;

int m,n,bk[100];
int check(int hi,int lo) {
	int i,h=0,s;
	for (i=0;i<m;i++) {
		s=0;
		while(true) if (s+bk[h]<=(hi+lo)/2 && h<n) s+=bk[h++]; else break;
	}
	if (h==n) return 1;
	return 0;
}
int main() {
    int hi,lo,i;
    while(cin >> m >> n) {
		if (m==0) break;
		hi= 1500000; lo=0;
		for (i=0;i<n;i++) cin >> bk[i];
		for (i=0;i<22;i++) if (check(hi,lo)==1) hi=(hi+lo)/2; else lo=(hi+lo)/2;
		cout << hi << 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( w < t ){
				w = t;
			}
		}
		if( sum / m > WIDTH_LIMIT ){
			width = w;
		}else{
			width = ( sum / m > w ? sum / m : 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 && e + width < WIDTH_LIMIT ){
				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>
#include<vector>
using namespace std;
int n,m;
vector<int> v;
bool f(int sz){
	int temp=sz;
	int ret=1;
	for(int i=0;i<m;i++){
		if(sz-v[i]>=0){
			sz-=v[i];
		}else{
			ret++;
			sz=temp-v[i];
		}
	}
	return ret<=n;
}
int main(){
	
	while(cin>>n>>m,n||m){
		v=vector<int>(m);
		int l=1000000000,r=0;
		for(int i=0;i<m;i++){
			cin>>v[i];
			r+=v[i];
			l=min(l,v[i]);
		}
		
		while(r>l){
			int mid=(l+r)/2;
			if(f(mid)){
				r=mid;
			}else{
				l=mid+1;
			}
			
		}
		cout<<r<<endl;
	}
	return 0;
}