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
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define s second
#define f first

const int N=3e5+5;
priority_queue <pair<ll,int>> wol[N]; // wolne to suma k elem 
vector <ll> luz, waros; 
bool zaj[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll ilesto, ilewar, war, ile;
    ll sum=0, lacz=0, odp=0;
    cin >> ilesto >> ilewar >> ile;
    for( int i=0; i<ilesto; ++i ){
        waros.clear();
        for( int j=0; j<ilewar; ++j ){
            cin >> war;
            waros.push_back( war );
        }
        if( waros.back() > waros[0] ){
            sum=0;
            for( int j=0; j<=waros.size(); ++j ){
                wol[j].push({sum,i});
                if( j == waros.size() )
                    break;
                sum += waros[j];
            }
            lacz++;
        }
        else{
            for( ll w : waros )
                luz.push_back(w);
        }
    }
    sum=0;
    sort( luz.begin(), luz.end() );
    luz.push_back(0);
    reverse( luz.begin(), luz.end() );
    for( int i=1; i<luz.size(); ++i )
        luz[i] += luz[i-1];
    for( int i=0; i<lacz; ++i ){
        if( i*ilewar > ile )
            break;
        for( int j=0; j<ilewar; ++j ){
            if( i*ilewar + j > ile )
                break;
            while( zaj[wol[j].top().s] )
                wol[j].pop();
            // cerr << i << ' ' << j << ' ' << wol[j].top().f << ' ' << sum << ' ' << ile-(i*ilewar+j) << ' ' << wol[j].top().f+sum+luz[min((ll)luz.size()-1,ile-(i*ilewar+j))] << '\n';
            odp = max( odp, wol[j].top().f+sum+luz[min((ll)luz.size()-1,ile-(i*ilewar+j))] );
        }
        sum += wol[ilewar].top().f;
        zaj[wol[ilewar].top().s]=1;
        wol[ilewar].pop();
    }
    if( lacz*ilewar <= ile )
        odp = max( odp, sum+luz[min((ll)luz.size()-1,ile-(lacz*ilewar))] );
    cout << odp << '\n';

    return 0;
}