代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,k,a[N],f[N][N],wh[N][N],ans[N][2];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=2;i<=n;++i) a[i]+=a[i-1];
	for(int i=1;i<=n;++i) f[1][i]=a[i];
	for(int i=2;i<=k;++i)
		for(int j=1;j<=n;++j)
		{
			f[i][j]=1<<30;
			for(int k=0;k<=j;++k)
				if(max(f[i-1][k],a[j]-a[k])<f[i][j])
					f[i][j]=max(f[i-1][k],a[j]-a[k]),wh[i][j]=k;
		} 
	int now=n;
	for(int i=k; i;--i)
	{
		ans[i][1]=now;
		ans[i][0]=wh[i][now]+1;
		now=wh[i][now];
	}
	for(int i=1;i<=k;++i)
		printf("%d %d\n",ans[i][0],ans[i][1]);
	return 0;
}