fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pii pair<ll,ll>
  5. #define bien tuple<ll,ll,ll>
  6. const ll nmax=2e5+163,inf=1e18,mod=1e9+7,base=450;
  7. ll n,m,k;
  8. int main()
  9. {
  10.     ios_base::sync_with_stdio(0);
  11.     cin.tie(0); cout.tie(0);
  12.     //freopen("yoimiya.INP","r",stdin);
  13.     //freopen("yoimiya.OUT","w",stdout);
  14.     cin>>n>>m>>k;
  15.     vector<vector<ll>> a(n+5,vector<ll>(m+5,0));
  16.     vector<ll> inc,dec,sum(n+5,0),pref_sum(n+5),suff_pref(m+5,0),pref_best(m+5,-inf);
  17.     for (int i=1;i<=n;i++)
  18.     {
  19.         for (int j=1;j<=m;j++)
  20.             cin>>a[i][j];
  21.         if (a[i][1]<=a[i][m]) inc.push_back(i);
  22.         else dec.push_back(i);
  23.     }
  24.  
  25.     vector<ll> vecL(n*m+5,0);
  26.     ll it=0;
  27.     for (auto i:dec)
  28.         for (int j=1;j<=m;j++)
  29.             vecL[++it]=a[i][j];
  30.     sort(vecL.begin()+1,vecL.begin()+it+1,greater<ll>());
  31.     for (int i=1;i<=it;i++)
  32.         vecL[i]=vecL[i-1]+vecL[i];
  33.  
  34.  
  35.     vector<ll> vecR(n*m+5,0);
  36.     ll sz=inc.size();
  37.     for (auto i:inc)
  38.         for (int j=1;j<=m;j++)
  39.             sum[i]+=a[i][j];
  40.     sort(inc.begin(),inc.end(),[&](ll L,ll R)
  41.     {
  42.         return sum[L]>sum[R];
  43.     });
  44.     for (int i=1;i<=sz;i++) pref_sum[i]=pref_sum[i-1]+sum[inc[i-1]];
  45.     for (int i=0;i<=sz;i++) vecR[i*m]=pref_sum[i];
  46.     for (int i=sz-1;i>=0;i--)
  47.     {
  48.         ll id=inc[i],pref=0;
  49.         for (int j=1;j<m;j++)
  50.         {
  51.             pref+=a[id][j];
  52.             suff_pref[j]=max(suff_pref[j],pref);
  53.             vecR[i*m+j]=pref_sum[i]+suff_pref[j];
  54.         }
  55.     }
  56.     for (int i=0;i<sz;i++)
  57.     {
  58.         ll id=inc[i],pref=0;
  59.         for (int j=1;j<m;j++)
  60.         {
  61.             pref+=a[id][j];
  62.             vecR[i*m+j]=max(vecR[i*m+j],pref_sum[i+1]+pref_best[j]);
  63.             pref_best[j]=max(pref_best[j],pref-sum[id]);
  64.         }
  65.     }
  66.  
  67.     ll ans=-inf;
  68.     for (int i=0;i<=min(it,k);i++)
  69.     {
  70.         if (sz*m<k-i) continue;
  71.         ans=max(ans,vecL[i]+vecR[k-i]);
  72.     }
  73.     cout<<ans;
  74. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8MbOP8
language:
C++14 (gcc 8.3)
created:
2 days 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!