1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
long long n,m,k,a;
long long sum;
const long long MAX = 400000000000000000;
int main()
{
    std::ios_base::sync_with_stdio(0);
    cin>>n>>m>>k;
    vector<vector<long long> > whole;
    whole.resize(m, vector<long long> (n));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>whole[j][i];
            sum+=whole[j][i];
        }
    }
    if(2*k <= m*n){
        vector<long long> dp(k+1), ndp(k+1);
        for(int i=0;i<n;i++){
            for(int j=1;j<min(m,k);j++){
                whole[j][i]+=whole[j-1][i];
            }
        } 
        long long localMax=0;
        for(int j=1;j<=min(m,k);j++){
            for(int i=1;i<=n;i++){
                for(int p=min(k-j, localMax); p>=0; p--){
                    ndp[p+j] = max(ndp[p+j], dp[p] + whole[j-1][i-1]);
                }
                localMax += j;
            }
            dp = ndp;
        }
        cout<<dp[k];
    }
    else{
        k = m * n - k;
        vector<long long> dp(k+1, MAX), ndp(k+1, MAX);
        dp[0]=0;
        ndp[0]=0;
        for(int i=0;i<n;i++){
            for(int j=m-2;j>=max(0LL,m-k);j--){
                whole[j][i]+=whole[j+1][i];
            }
        }
        long long localMax = 0;
        for(int j=m-1;j>=max(0LL,m-k);j--){
            for(int i=1;i<=n;i++){
                for(int p=min(k-m+j, localMax); p>=0; p--){
                    ndp[p+m-j] = min(ndp[p+m-j], dp[p] + whole[j][i-1]);
                }
                localMax += m-j;
            }
            dp = ndp;
        }
        cout<<sum-dp[k];
    }
    return 0;
}