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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <deque>
#include <map>
#include <queue>
#include <climits>
using namespace std;
using ll=long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<ll>> V(N, vector<ll> (M));
    vector<bool> odw(N);
    for(int i=0; i<N; i++){
        bool odwrocone=false;
        int last=0;
        for(int j=0; j<M; j++){
            cin>>V[i][j];
            if(V[i][j]<last){
                odwrocone=true;
            }
            last=V[i][j];
        }
        odw[i]=odwrocone;
    }

    priority_queue<pair<pair<long double, pair<int, ll>>, pair<int, int>>,
    vector<pair<pair<long double, pair<int, ll>>, pair<int, int>>>> pq;
                  //wartosc, ilosc, wartosc, indeks , indeks
    ll wynik=0;
    for(int i=0; i<N; i++){
        if(odw[i]){
            for(int j=0; j<M; j++){
                //pair<pair<double, pair<int, int>>, pair<int, int>> a;
                pq.push({{double(V[i][j]), {1, V[i][j]}}, {i, j}});
            }
        }
        else{
            long double pref=0;
            for(int j=0; j<M; j++){
                pref+=V[i][j];
                pq.push({{pref/(j+1), {j+1, ll(pref)}}, {i, j}});
            }
        }
    }
    while(K>0){
        auto a = pq.top();
        pq.pop();
        if(a.first.second.first <=K){
            wynik+=a.first.second.second;
            K-=a.first.second.first;
        }
    }
    cout<<wynik<<'\n';


    return 0;
}