514D - R2D2 and Droid Army - CodeForces Solution

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
#include <unordered_set>
#include <queue>
#include <map>
#include <cmath>
#include <climits>
#include <iomanip>
#include <unordered_map>
#include <stdio.h>
#include <stack>
#include <list>
#include "complex"
#include <assert.h>

#define el '\n'
#define ll long long

using namespace std;
//
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//
//using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int N = 200005, mod = 1e9 + 7, MAX = 1e9 + 1, M = 1e5;
long double PI = 3.14159265358979323846;;
#define point  complex<long double>
#define vec(a, b) b-a
#define dot(a, b) (long double)(conj(a)*b).real()
#define cross(a, b) (long double)(conj(a)*b).imag()
#define length(a) (hypot((a).imag(), (a).real()))
#define angle(a) atan2((a).imag(), (a).real())
int h, w;
//char a[201][201];
//int dx[] = {0, 0, -1, 1, 1, -1, -1, 1}, dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};
//int dx[] = {-1, -1, 0, 0, 1, 1}, dy[] = {-1, 0, -1, 1, 0, 1};
//
//bool valid(int i, int j) {
//    return (i < h && i >= 0 && j < w && j >= 0);
//}
//
//bool vis[201][201];
//bool w1, w2;
//
//void dfs(int i, int j) {
//    if (j == 0)
//        w1 = 1;
//    if (j == w - 1)
//        w2 = 1;
//    vis[i][j] = 1;
//    for (int k = 0; k < 6; ++k) {
//        int ni = i + dx[k], nj = j + dy[k];
//        if (valid(ni, nj) && a[ni][nj] == 'w' && !vis[ni][nj])
//            dfs(ni, nj);
//    }
//}
//ll mul(ll a, ll b) {
//    return ((a % mod) * (b % mod)) % mod;
//}
//
//ll add(ll a, ll b) {
//    return ((a % mod) + (b % mod)) % mod;
//}
//
//ll sub(ll a, ll b) {
//    return ((((a + mod) % mod) - ((b + mod) % mod)) + mod) % mod;
//}
//
int n, a[N][5], lg[N], q;

struct {
    int table[N][20][5];

    void build(int m) {
        lg[1] = 0;
        for (int i = 2; i <= n; ++i) {
            lg[i] = lg[i / 2] + 1;
        }
        for (int i = 0; i < n; ++i)
            table[i][0][m] = a[i][m];

        for (int j = 1; j < 20; j++) {
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                table[i][j][m] = max(table[i][j - 1][m], table[i + (1 << (j - 1))][j - 1][m]);
            }
        }
    }

    int query(int l, int r, int m) {
        int sz = r - l + 1, j = lg[sz];
        return max(table[l][j][m], table[r - (1 << j) + 1][j][m]);
    }

} spt;

//
//struct {
//    ll tree[N], lazy[N * 4] = {0}, neu = 1e18;
//
//    ll merge(int a, int b) {
//        return min(a, b);
//    }
//
//    void build(int node, int start, int end) {
//        if (start == end) {
//            tree[node] = a[start];
//            return;
//        }
//        int mid = (start + end) / 2;
//        build(node * 2, start, mid);
//        build(node * 2 + 1, mid + 1, end);
//        tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
//    }
//
//    void propagate(int node, int st, int en) {
//        tree[node] += lazy[node];
//        if (st != en) {
//            lazy[node * 2] += lazy[node];
//            lazy[node * 2 + 1] += lazy[node];
//        }
//        lazy[node] = 0;
//    }
//
//    ll query(int node, int st, int en, int l, int r) {
//        if (l > en || r < st)return neu;
//        propagate(node, st, en);
//        if (l <= st && r >= en) {
//            //     cout << node << ' ' << tree[node] << '\n';
//            return tree[node];
//        }
//
//        int mid = (st + en) / 2;
//        ll x = query(node * 2, st, mid, l, r);
//        ll xx = query(node * 2 + 1, mid + 1, en, l, r);
//        return merge(x, xx);
//    }
//
//
//    void update_range(int node, int st, int en, int l, int r, int val) {
//        propagate(node, st, en);
//        if (l > en || r < st)return;
//        if (st >= l && r >= en) {
//
//            tree[node] += val;
//
//            if (st != en) {
//                lazy[node * 2] += val;
//                lazy[node * 2 + 1] += val;
//            }
//            return;
//        }
//        int mid = (st + en) / 2;
//        update_range(node * 2, st, mid, l, r, val);
//        update_range(node * 2 + 1, mid + 1, en, l, r, val);
//        tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
//    }
//} segTree;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < m; ++i) {
        spt.build(i);
    }
    ll sum;
    int l, r, ans = 0;
    for (int i = 0; i < n; ++i) {
        int mid, st = i, en = n - 1;
        while (st <= en) {
            mid = (st + en) / 2;
            sum = 0;
            for (int j = 0; j < m; ++j)
                sum += (ll) spt.query(i, mid, j);

            if (sum <= k) {
                //      cout << i << ' ' << mid << '\n';
                if (mid - i + 1 > ans)l = i, r = mid;
                ans = max(ans, mid - i + 1);
                st = mid + 1;
            } else
                en = mid - 1;
        }
    }
    if (ans) {
        for (int i = 0; i < m; ++i)
            cout << spt.query(l, r, i) << ' ';
    } else {
        for (int i = 0; i < m; ++i)
            cout << 0 << ' ';

    }
    return 0;
}