Submission #1224207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224207		12345678	Olympiads (BOI19_olympiads)	C++20	13 / 100	2092 ms	1684 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

const int nx=505;

int n, k, c, used[nx], dp[nx][nx], tmp;

struct students
{
    int s, idx, a[6];
    bool operator< (const students &o) const {return s<o.s;}
} s[nx];
students sub[6][nx];
vector<students> req;
multiset<int> ms;

void bruteforce(int idx, vector<int> cur, int cnt)
{
    //cout<<"dbg "<<idx<<'\n';
    if (idx==n)
    {
        if (cnt==k)
        {
            tmp++;
            int sm=0;
            for (auto x:cur) sm+=x;
            ms.insert(sm);
            if (ms.size()>c) ms.erase(ms.begin());
        }
        return;
    }
    if (cnt<k) 
    {
        vector<int> tmp(k);
        for (int i=0; i<k; i++) tmp[i]=max(cur[i], req[idx].a[i]);
        bruteforce(idx+1, tmp, cnt+1);
    }
    bruteforce(idx+1, cur, cnt);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k>>c;
    dp[0][0]=1;
    for (int i=1; i<=n+1; i++) for (int j=0; j<=i; j++) dp[i][j]=dp[i-1][j]+(j?dp[i-1][j-1]:0); //cout<<"dp "<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
    for (int i=0; i<n; i++) for (int j=0; j<k; j++) cin>>s[i].a[j];
    for (int i=0; i<k; i++) for (int j=0; j<n; j++) sub[i][j]=s[j], sub[i][j].s=s[j].a[i], sub[i][j].idx=j;
    for (int i=0; i<k; i++) sort(sub[i], sub[i]+n), reverse(sub[i], sub[i]+n);
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<k; j++)
        {
            if (!used[sub[j][i].idx]&&dp[req.size()+1][k]<3000000)
            {
                used[sub[j][i].idx]=1;
                req.push_back(sub[j][i]);
            }
        }
    }
    //cout<<"debug "<<req.size()<<'\n';
    bruteforce(0, vector<int>(k), 0);
    //cout<<"end "<<tmp<<' '<<dp[req.size()][k]<<'\n';
    if (tmp!=dp[req.size()][k]) cout<<1/0;
    auto itr=prev(ms.end());
    while (--c) --itr;
    cout<<*itr;
}

/*
5 3 4
7 0 4
3 0 8
1 1 3
5 1 3
4 2 2

*/

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:65:40: warning: division by zero [-Wdiv-by-zero]
   65 |     if (tmp!=dp[req.size()][k]) cout<<1/0;
      |                                       ~^~

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