2662 기업투자

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int arr[1000][1000] = { 0 };
int dp[1000][1000] = { 0 };
int company[1000][1000] = { 0 };
 
void post(int m, int n) {
    if (n > 0) {        
        post(m - company[m][n], n - 1);
        printf("%d ", company[m][n]);
    }    
}
 
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    getchar();
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 1; i <= n; i++) {        
        for (int j = 1; j <= m; j++) {
            int maxNum = 0;
            for (int k = 0; k <= j; k++) {
                if (maxNum < dp[k][i-1] + arr[j - k][i]) {
                    company[j][i] = j - k;
                    maxNum = dp[k][i-1] + arr[j - k][i];
                }
            }
            dp[j][i] = maxNum;
        }        
    }
    
    printf("%d\n", dp[m][n]);
    post(m, n);
}