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<cstdio>
#include<algorithm>
using namespace std;
int books[128];
int m,n;
bool check(int mid){
	int now = 0;//現在の添字
	int d = 0;//現在の棚
	int l = 0;//現在の棚の幅
	while(now < n && d < m){
		if(l + books[now] <= mid){
			l += books[now++];
		}
		else{
			d++;
			l = 0;
		}
	}
	if(d > m-1)return false;
	else return true;
}
int main(){
	while(scanf("%d%d",&m,&n),(m|n)){
		int sum = 0;
		int ma = -1000;
		for(int i = 0; i < n; i++){
			scanf("%d",&books[i]);
			sum += books[i];
			ma = max(ma,books[i]);
		}
		
		int l = ma,r = sum;
		int mid=0;
		for(int i = 0;i < 100; i++){
			mid = (l+r)/2;
			if( check(mid) ){
				r = mid;
			}
			else l = mid;
		}
		printf("%d\n",r);
	}
	return 0;
}

C++: #include <iostream>
#include<cstdio>
#include <cstring>	// require memset
#include <fstream>	// require freopen

using namespace std;

const int MaxW = 1500000;
int m, n;	// {IÌi 1  m  20, {Ìª 1  n  100
int w[100];

bool calc_m (int curr_w )
{
	int l[20];
	memset (l, 0, sizeof (l ) );

	int j = 0;
	for (int i = 0; i < n; i++ ){
		while (j < m && l[j] + w[i] > curr_w )
			j++;
		if (j == m )
			return false;
		l[j] += w[i];
	} // end for

	return true;
}

int main()
{
//	cut here before submit 
//	freopen ("testcase.persistence", "r", stdin );

	for (;; ){// {IÌ ans  1500000
		scanf ("%d%d", &m, &n ); if (!m ) break;
		memset (w, 0, sizeof (w ) );

		for (int i = 0; i < n; i++ ){
			scanf ("%d", w+i );
		} // end for
		int l = w[0];
		int r = MaxW;
		int mid = 0;
		int res = MaxW;
		while (l <= r ){
			mid = (l+r)/2;
			if (calc_m (mid ) ){
				res = min (res, mid );
				r = mid-1;		
			}else{
				l = mid+1;
			} // end if
		} // end while
		cout << res << endl;
	} // end loop
		
	return 0;
}

C++: #include<iostream>
using namespace std;
int s[1001];
int b[1001];
int m, n;
int nb;
int w;
//find max x s[x]<=w+s[nb-1];
int se() {
	int be = nb;
	int en = n;
	int bb=-1;
	int ee = -1;
	for (; en - be>0;) {
		int mid = (be + en) / 2;
		if (w + s[nb-1] >= s[mid]) {
			be = mid;
			if (bb == be)
				en--;
			else
				bb = be;

		}
		else {
			en = mid;
			if (ee == en)
				en--;
			else
				ee = en;
		}
		

	}
	
	if (be + 1 <= n)
		if (s[be+1] <= w + s[nb - 1])
			return be + 1;
	if (s[be] <= w + s[nb - 1])
		return be;
	else
		return -1000;
}

int main() {
	s[0] = 0;
	while (cin >> m >> n, m) {
		int i;
		int nm;
		for (i = 0; i < n; i++)
			cin >> b[i];
		for (i = 1; i <= n; i++)
			s[i] = s[i - 1] + b[i-1];
		for (w = 1; w <= 1500000; w++) {
			nb = 1;
			for (nm = 1; nm <= m&&nb<=n; nm++) {
				nb = se();
				if (nb < 0)
					break;
				nb++;
				
			}
			if (nb > n)
				break;

		}
		cout << w << endl;




	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#define ALL(A) A.begin(), A.end()

using namespace std;

int main()
{
	int m, n;	// {IÌi 1  m  20, {Ìª 1  n  100

	while (cin >> m >> n && m && n ){
		vector <int> w (n, 0 );	// {Ì 1  w[i]  1000000
		int res = 0;				// {IÌ ans  1500000
		for (int i = 0; i < n; i++ ){
			cin >> w[i];
		} // end for

		if (m >= n ){
			res = w[max_element (ALL(w)) - w.begin()];
		}else{
			int curr_w = w[0];
			for (int i = 1; i < n; i++ ){
				curr_w += w[i];
				int cm = 1;
				int j = i+1;
				while (j < n && cm <= m ){
					int cw = 0;
					while (cw + w[j] <= curr_w && j < n ){
						cw += w[j];
						j++;
					} // end while
					cm++;
				} // end while
				if (cm <= m ){
					res = curr_w;
					break;
				} // end if
			} // end for
		} // end if

		cout << res << endl;

	} // end loop
		
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <climits>
#include <vector>

int m, n;
int w[100];

std::vector< std::vector<int> > memo(21, std::vector<int>(101));

const int MAX_WIDTH = 1500000;


int dfs(int i, int j){
    if(memo[i][j] != -1){
        return memo[i][j];
    }

    if(i >= m){
        return memo[i][j] = ( (j<n) ? -1 : 0 );
    }
    if(j >= n){
        return memo[i][j] = 0;
    }

    int ans = INT_MAX;

    int width = 0;
    int res;
    for(int k=j; k<n; ++k){
        width += w[k];

        res = dfs(i+1, k+1);
        if(res >= 0){
            ans = std::min(ans, std::max(width,res));
        }
    }

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

int main(void){
    while(std::cin >> m >> n){
        if(m == 0 && n == 0) break;
        for(int i=0; i<n; ++i){
            std::cin >> w[i];
        }

        for(int i=0; i<=m; ++i){
            for(int j=0; j<=n; ++j){
                memo[i][j] = -1;
            }
        }
        std::cout << dfs(0,0) << std::endl;
    }
}

C++: #include<iostream>
using namespace std;
int n, m;
int a[101];
bool search(int v);
int main()
{	
	cin >> m >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	int l, r;
	l = 0; r = 1 << 24;
	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>
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
using namespace std;
bool ok(int m, int n, int s[100], int width) {
	int cnt = 0, size = s[0];
	rep2(i,1,n) {
		if(width<size) return false;
		if(width<size+s[i]) {
			size = 0;
			cnt++;
		}
		size += s[i];
	}
	if(size>0)cnt++;
	if(m>=cnt) return true;
	return false;
}
int main(){
	int m, n;
	while(cin >> m >> n, (m||n)) {
		int s[100] = {};
		rep(i,n) {
			cin >> s[i];
		}
		int lo = 0, hi = 1500000;
		while(hi-lo>1) {
			int mid = (hi+lo)/2;
			if(ok(m,n,s,mid)) hi = mid;
			else lo = mid;
		}
		cout << hi << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <climits>

using namespace std;

bool a(vector < int > book, int mid, int m) {
	vector < int > total(m);
	int count = 0;

	for(int i = 0; i < m; i++) {
		for(int j = count; j < book.size(); j++) {
			total[i] += book[j];
			count++;
			if(total[i] > mid) {
				total[i] -= book[j];
				count--;
				break;
			}
		}
	}

	if(count == book.size()) {
		return true;
	} else {
		return false;
	}
}

int main() {
	int n, m;

	

	while ( true ) {
		cin >> m >> n;

		if(!m && !n) {
			break;
		}
		vector < int > book(n);

		for(int i = 0; i < n; i++) {
			cin >> book[i];
		}

		int bottom = 0, top = 1500000;

		for(int i = 1; i <= 100; i++) {
			int mid = (bottom + top) / 2;
			if( a(book, mid, m) ) {
				top = mid;
			} else {
				bottom = mid + 1;
			}
		}

		cout << (bottom + top) / 2 << endl;
	}
}