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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);

   int n, m, k;
   cin >> n >> m >> k;
   int T = n * m;

   vector nums(n, vector<long long>(m, 0));
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         cin >> nums[i][j];
      }
   }

   vector<long long> decs;
   vector<vector<long long>> inc;
   for (int i = 0; i < n; i++) {
      bool dec = true;
      for (int j = 1; j < m; j++) {
         if (nums[i][j - 1] < nums[i][j]) { dec = false; break; }
      }
      vector<long long> pre(m + 1);
      for (int j = 0; j < m; j++) {
         pre[j + 1] = pre[j] + nums[i][j];
      }
      if (!dec) {
         inc.push_back(pre);
      }
      else {
         for (auto a : nums[i]) decs.push_back(a);
      }
   }

   sort(decs.begin(), decs.end(), greater<long long>());
   sort(inc.begin(), inc.end(),
   [](vector<long long> &v1, vector<long long> &v2) {
         return *(v1.rbegin()) > *(v2.rbegin());
   });

   int sz = (int)inc.size();
   vector<long long> suf(T + 1);

   for (int t = 0; t < m; t++) {
      long long sum = 0;
      long long mini = 1e12;
      for (int i = 0; i < sz; i++) {
         sum += inc[i][m];
         mini = min(mini, inc[i][m] - inc[i][t]);
         suf[i*m+t] = max(suf[i*m+t], sum - mini);
      }

      suf[sz*m] = sum;

      long long maxi = 0;
      for (int i = sz - 1; i >= 0; i--) {
         sum -= inc[i][m];
         maxi = max(maxi, inc[i][t]);
         suf[i*m+t] = max(suf[i*m+t], sum + maxi);
      }
   }

   vector<long long> pre(T + 1);
   for (int i = 0; i < (int)decs.size(); i++) {
      pre[i + 1] = pre[i] + decs[i];
   }

   long long out = 0;
   for (int i = 0; i <= k; i++) {
      out = max(out, pre[i] + suf[k - i]);
   }

   cout << out << '\n';

   // for (auto v : inc) { for (auto a : v) { cerr << a << ' '; } cerr << endl; }
   // for (auto a : suf) { cerr << a << ' '; } cerr << endl;
   // for (auto a : pre) { cerr << a << ' '; } cerr << endl;

   return 0;
}