Submission #1248095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248095		bncodero_o123	Olympiads (BOI19_olympiads)	C++20	100 / 100	37 ms	10852 KiB

olympiads

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define name "code"
using namespace std;

int n, k, c;
int a[502][8];
bool vis[502];

int get(int id) {
    int ans= 0;
    for(int i= 1; i <= n; ++i)
        if(!vis[i])
            if(!ans || (ans && a[ans][id] < a[i][id]))
                ans= i;
    return ans;
}

struct PARTITION {
    vector<int> choices, con;
    int score, ex;

    bool operator < (PARTITION other) const {
        return score < other.score;
    }

    PARTITION(vector<int> _choices= vector<int> (n + 2, 0)) : choices(_choices) {
        con.resize(k + 2, 0);
        fill_n(vis, n + 2, 0);
        score= ex= 0;

        for(int i= 1; i <= n; ++i)
            if(choices[i] != 0) {
                if(choices[i] > 0) con[choices[i]]= i;
                ex += choices[i] == -1;
                vis[i]= 1;
            }

        for(int i= 1; i <= k; ++i)
            if(!con[i]) {
                con[i]= get(i);
                vis[con[i]]= 1;
            }

        for(int i= 1; i <= k; ++i) {
            int mx= 0;
            for(int j= 1; j <= k; ++j)
                mx= max(mx, a[con[j]][i]);
            score += mx;
        }
    }
};

void solve() {
    cin >> n >> k >> c;
    for(int i= 1; i <= n; ++i)
        for(int j= 1; j <= k; ++j)
            cin >> a[i][j];

    priority_queue<PARTITION> pq;
    pq.push(PARTITION());

    while(c--) {
        PARTITION p= pq.top(); pq.pop();
        if(c == 0) return (void)(cout << p.score << '\n');

        if(p.ex < n - k)
            for(int i= 1; i <= k; ++i)
                if(p.choices[p.con[i]] == 0) {
                    vector<int> choices= p.choices;
                    choices[p.con[i]]= -1;
                    for(int j= 1; j < i; ++j) choices[p.con[j]]= j;
                    PARTITION _p= PARTITION(choices);
                    pq.push(_p);
                }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    int T= 1;
    for(; T; --T) solve();

    return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32