记录编号	370354	评测结果	AAAAAAAAAA
题目名称	书的复制	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-02-13 16:38:44	内存使用	0.00 MiB

//KZNS
#include <cstdio>
#define max(a, b) (a < b ? b : a)
#define min(a, b) (a < b ? a : b)
#define Mmax 503
int M, K;
int T[Mmax];
int F[Mmax][Mmax];
int S[Mmax][Mmax];
void init() {
    scanf("%d %d", &M, &K);
    for (int i = 1; i <= M; i++) {
        scanf("%d", &T[i]);
        T[i] += T[i-1];
    }
}
void pf(int a, int b) {
    if (S[a][b])
        pf(a-1, S[a][b]);
    printf("%d %d\n", S[a][b]+1, b);
}
void solve() {
    for (int i = 1; i <= M; i++) {
        F[1][i] = T[i];
        S[1][i] = 0;
    }
    for (int k = 2; k <= K; k++) {
        int j = k-1;
        for (int i = k; i <= M; i++) {
            if (T[i] - T[j] <= F[k-1][j]) {
                F[k][i] = F[k-1][j];
                S[k][i] = j;
            }
            else {
                for (j++; j <= i; j++) {
                    if (T[i] - T[j] <= F[k-1][j]) {
                        if (T[i] - T[j-1] < F[k-1][j]) {
                            F[k][i] = T[i] - T[j-1];
                            S[k][i] = j-1;
                        }
                        else {
                            F[k][i] = F[k-1][j];
                            S[k][i] = j;
                        }
                        break;
                    }
                }
            }
        }
    }
    pf(K, M);
}
int main() {
    freopen("books.in", "r", stdin);
    freopen("books.out", "w", stdout);
    init();
    solve();
    return 0;
}
//UBWH