Submission #1330999

#TimeUsernameProblemLanguageResultExecution timeMemory
1330999edoOlympiads (BOI19_olympiads)C++20
44 / 100
2094 ms344 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, k, c;
int a[501][6];
int s[501][6];

priority_queue<int, vector<int>, greater<>> q;

void dfs(int start, int d, int mx[], int curr) {
    if(d == k) {
        if(q.size() < c) 
            q.push(curr);
        else if(curr > q.top()) {
            q.pop();
            q.push(curr);
        }
        return;
    }

    int rem = k - d;
    if(rem > n - start) return;

    int ub = 0;
    for(int i = 0; i < k; i++) 
        ub += max(mx[i], s[start][i]);

    if(q.size() == c && q.top() >= ub) return;

    for(int i = start; i < n - rem + 1; i++) {
        int nmx[6], score = 0;
        for(int j = 0; j < k; j++) {
            nmx[j] = max(mx[j], a[i][j]);
            score += nmx[j];
        }
        dfs(i + 1, d + 1, nmx, score);
    } 
}

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

    cin >> n >> k >> c;
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < k; j++) 
            cin >> a[i][j];

    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y) {
                int s1 = 0, s2 = 0;
                for(int i = 0; i < k; i++) { s1 += a[x][i]; s2 += a[y][i]; }
                return s1 > s2;
            });
    
    {
    int tmp[501][6];
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < k; j++) 
            tmp[i][j] = a[idx[i]][j];

    for(int i = 0; i < n; i++) 
        for(int j = 0; j < k; j++) 
            a[i][j] = tmp[i][j];
    }


    for(int i = n - 1; ~i; i--) 
        for(int j = 0; j < k; j++) 
            s[i][j] = max(a[i][j], s[i + 1][j]);

    int mx[6] {};
    dfs(0, 0, mx, 0);

    cout << q.top();

    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...