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>
#include<vector>
#include<algorithm>
using namespace std;
bool check(int n,int wei,vector<int> book)
{
  int tmp=wei;
  n--;
  for(int i=0;i<book.size();i++)
    {
      if(tmp<book[i])
	{
	  if(n>0)
	    {
	      n--;
	      tmp=wei;
	      if(tmp<book[i])
		return false;
	    }
	  else
	    return false;
	}
      //  cout<<n<<" "<<tmp<<" "<<book[i]<<endl; 
      tmp-=book[i];
    }
  return true;
}
int main()
{
  int m,n;
  for(;cin>>m>>n,m;)
    {
      vector<int> book;
      for(int i=0;i<n;i++)
	{
	  int tmp;
	  cin>>tmp;
	  book.push_back(tmp);
	}
      /*
      while(true)
	{
	  int tmp;
	  cin>>tmp;
	  if(check(m,tmp,book))
	      cout<<"YES"<<endl;
	  else
	      cout<<"NO"<<endl;
	}
      */

      int l=0;
      int r=1500000;
      int ans;
      while(l<r)
	{
	  //	  cout<<l<<" "<<r<<endl;
	  // cout<<(l+r)/2<<endl;
	  if(check(m,(l+r)/2,book))
	    {
	      ans=(l+r)/2;
	      if(r==(l+r)/2)
		break;
	      r=(l+r)/2;

	    }
	  else
	    {
	      if(l==(l+r)/2)
		break;
	      l=(l+r)/2;
	    }
	}
      cout<<ans<<endl;

    }
}

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 <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int M, N, width[110];
int dp[110][110][25];

signed main() {
    while(cin >> M >> N, M) {
        fill(dp[0][0], dp[N][N], INF);
        for(int i=0; i<N; i++) {
            cin >> width[i];
        }

        for(int i=0; i<N; i++) {
            int sum = 0;
            for(int j=i; j<N; j++) {
                sum += width[j];
                dp[i][j+1][1] = sum;
            }
        }

        for(int d=2; d<=N; d++) {
            for(int l=0; l<N-d+1; l++) {
                int r = l + d;
                int mi = INF;
                for(int m=2; m<=M; m++) {
                    chmin(dp[l][r][m], mi);
                    for(int k=l+1; k<r; k++) {
                        for(int p=1; p<m; p++) {
                            int vl = dp[l][k][p  ];
                            int vr = dp[k][r][m-p];
                            chmin(dp[l][r][m], max(vl, vr));
                        }
                    }
                    chmin(mi, dp[l][r][m]);
                }
            }
        }
        cout << dp[0][N][M] << endl;
    }
    return 0;
}

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

int DP[100][20];
int main()
{
	int n,m;
	while(cin >> m >> n){
		if(!m && !n)
			break;
		for(int i=0;i<n;i++){
			int book;
			cin >> book;
			if(i==0)
				for(int j=0;j<m;j++){
					DP[i][j] = book;
				}
			else{
				DP[i][0] = DP[i-1][0]+book;
			}
		}
		
		for(int i=1;i<=n;i++){
			for(int j=1;j<m;j++){
				DP[i][j] = max(DP[i][0]-DP[i-1][0],DP[i-1][j-1]);
				for(int k=i-2;k>=0;k--){
					if(DP[i][0]-DP[k][0] >= DP[k][j-1]){
						DP[i][j] = min(DP[i][j],DP[i][0]-DP[k][0]);
						break;
					}else{
						DP[i][j] = min(DP[i][j],DP[k][j-1]);
					}
				}
			}
		}
		
		cout << DP[n-1][m-1] << endl;
	}
	return 0;
}