fork download 
  1. // Src : Vux2Code
  2. /* Note : 1
  3.     none
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. template <typename T> void vout(T s){ cout << s << endl; exit(0);}
  11.  
  12. typedef long long ll;
  13. typedef long double ld;
  14. typedef pair <ll, ll> pll;
  15.  
  16. const ll maxN = 20 + 5, maxLog = 20, inf64 = 1e18, mod = 1e9 + 7, maxW = 1e5 + 5;
  17.  
  18. ll t = 1;
  19.  
  20. ll n, m, w, b [maxN], a [maxN] [maxN], f [maxN] [maxN] [maxW];
  21.  
  22. void sortCol (ll x) {
  23.     for (int i = 1; i <= n; i ++) b [i] = a [i] [x];
  24.     sort (b + 1, b + n + 1);
  25.     for (int i = 1; i <= n; i ++) a [i] [x] = b [i];
  26. }
  27.  
  28. void solve () {
  29.     cin >> n >> m >> w;
  30.     for (int i = 1; i <= n; i ++) {
  31.         for (int j = 1; j <= m; j ++) {
  32.             cin >> a [i] [j];
  33.         }
  34.     }
  35.     a [1] [0] = inf64;
  36.     f [0] [0] [0] = 1;
  37.     for (int j = 1, tmp; j <= m; j ++) {
  38.         sortCol (j);
  39.         tmp = 0;
  40.         for (int i = 1; i <= n; i ++) {
  41.             while (tmp < n && a [tmp + 1] [j - 1] < a [i] [j]) tmp ++; 
  42.             // cerr << i << ' ' << j  << ' ' << tmp << '\n';
  43.             for (int k = a [i] [j]; k <= w; k ++) f [i] [j] [k] = max (f [i] [j] [k], f [tmp] [j - 1] [k - a [i] [j]]);
  44.             for (int k = a [i] [j]; k <= w; k ++) f [i] [j] [k] = max (f [i] [j] [k], f [i - 1] [j] [k - a [i] [j] + a [i - 1] [j]]);
  45.         }
  46.     }
  47.     // cerr << "Sorted Board : \n";
  48.     // for (int i = 1; i <= n; i ++) {
  49.     //     for (int j = 1; j <= m; j ++) {
  50.     //         cerr << a [i] [j] << ' ';
  51.     //     }
  52.     //     cerr << '\n';
  53.     // }
  54.     // for (int i = 1; i <= n; i ++) {
  55.     //     for (int j = 1; j <= m; j ++) {
  56.     //         cerr << i << ' ' << j << " : " << a [i] [j] << " : ";
  57.     //         for (int k = 0; k <= w; k ++) cerr << f [i] [j] [k] << ' ';
  58.     //         cerr << '\n';
  59.     //     }
  60.     // }
  61.     ll ans = -1;
  62.     for (int j = 1; j <= n; j ++) for (int i = 0; i <= w; i ++) if (f [j] [m] [i]) ans = i;
  63.     cout << ans;
  64. }
  65.  
  66. int main () {
  67.     ios::sync_with_stdio (0);
  68.     cin. tie (0);
  69.     cout. tie (0);
  70.     // #define TASK "task"
  71.     // freopen (TASK".inp", "r", stdin);
  72.     // freopen (TASK".out", "w", stdout);
  73.     // cin >> t;
  74.     while (t --) solve ();
  75. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/Aum5ct
language:
C++14 (gcc 8.3)
created:
80 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!