fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. vector<vector<int>> ups;
  6. vector<vector<int>> nups;
  7. vector<vector<int>> downs;
  8. vector<int> sups;
  9. vector<pair<int,int>> zups;
  10. int n,m;
  11. int solvedown[300009];
  12.  
  13. int solve_on_ups(int k) {
  14.     int sum = 0;
  15.     int q = sups.size();
  16.     int mx = k/m;
  17.     mx = min(mx, q);
  18.     for (int i = 0; i<mx; i++) {
  19.         sum += sups[i];
  20.     }
  21.     int best = sum;
  22.         for (int i = 0; i<q; i++) {
  23.             int s = sum;
  24.             if (i < mx) {
  25.                 s -= sups[i];
  26.                 if (mx < q) {
  27.                     s += sups[mx];
  28.                 }
  29.             }
  30.             for (int j = 0; j<k%m; j++) {
  31.                 s += nups[i][j];
  32.             }
  33.             best = max(best,s);
  34.         }
  35.     return best;
  36. }
  37.  
  38. int32_t main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(NULL);
  41.     cout.tie(NULL);
  42.     int k;
  43.     cin>>n>>m>>k;
  44.     vector<vector<int>> v;
  45.  
  46.     vector<bool> up;
  47.     if (m == 1) {
  48.         vector<int> q;
  49.         for (int i = 0; i<n*m; i++) {
  50.             int x;
  51.             cin>>x;
  52.             q.push_back(x);
  53.         }
  54.         sort(q.begin(), q.end(),greater<int>());
  55.         int s = 0;
  56.         for (int i = 0; i<k; i++) {
  57.             s += q[i];
  58.         }
  59.         cout<<s<<"\n";
  60.         return 0;
  61.     }
  62.     for(int i=0;i<n;i++) {
  63.         v.emplace_back();
  64.         int where = 0;
  65.         for (int j = 0; j < m; j++) {
  66.             int x;
  67.             cin>>x;
  68.             v[i].push_back(x);
  69.             if (j != 0) {
  70.                 if (v[i][j] > v[i][j-1]) {
  71.                     where = 1;
  72.                 }
  73.             }
  74.         }
  75.         if (where == 1) {
  76.             up.push_back(true);
  77.             ups.push_back(v[i]);
  78.             nups.emplace_back();
  79.         }else {
  80.             up.push_back(false);
  81.             downs.push_back(v[i]);
  82.         }
  83.     }
  84.     int i = 0;
  85.     for (auto x: ups) {
  86.         int h = 0;
  87.         for (auto q : x) {
  88.             h+=q;
  89.         }
  90.         sups.push_back(h);
  91.         zups.push_back({h,i});
  92.         i++;
  93.     }
  94.     sort(zups.begin(),zups.end(),greater<pair<int,int>>());
  95.     for (int i = 0; i<zups.size(); i++) {
  96.         nups[i] = ups[zups[i].second];
  97.     }
  98.     sort(sups.begin(), sups.end(),greater<int>());
  99.     vector<int> d;
  100.     for (auto x: downs) {
  101.         for (auto y: x) {
  102.             d.push_back(y);
  103.         }
  104.     }
  105.     sort(d.begin(), d.end(),greater<int>());
  106.     for (int i = 1; i<=k; i++) {
  107.         if (i-1 < d.size()) {
  108.             solvedown[i] = solvedown[i-1] + d[i-1];
  109.         }else {
  110.             solvedown[i] = solvedown[i-1];
  111.         }
  112.     }
  113.     int best = 0;
  114.     for (int i = 0; i<=k; i++) {
  115.         int a = solve_on_ups(i);
  116.         int b = solvedown[k-i];
  117.         best = max(best,a+b);
  118.     }
  119.     cout<<best<<"\n";
  120. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2 4 7
4 6 7 8
1 2 7 10
stdout
copy 
37
https://ideone.com/XrYw2t
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!