Submission #1224225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224225		12345678	Olympiads (BOI19_olympiads)	C++20	44 / 100	500 ms	1640 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

const int nx=505;

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

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;

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]<7000000)
            {
                used[sub[j][i].idx]=1;
                req.push_back(sub[j][i]);
            }
        }
    }
    int sz=req.size();
    for (int A=0; A<sz; A++)
    {
        if (k==1)
        {
            int sm=0;
            for (int i=0; i<k; i++) sm+=req[A].a[i];
            ms.insert(sm);
            if (ms.size()>c) ms.erase(ms.begin());
            continue;
        }
        for (int B=A+1; B<sz; B++)
        {
            if (k==2)
            {
                int sm=0;
                for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i]});
                ms.insert(sm);
                if (ms.size()>c) ms.erase(ms.begin());
                continue;
            }
            for (int C=B+1; C<sz; C++)
            {
                if (k==3)
                {
                    int sm=0;
                    for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i], req[C].a[i]});
                    ms.insert(sm);
                    if (ms.size()>c) ms.erase(ms.begin());
                    continue;
                }
                for (int D=C+1; D<sz; D++)
                {
                    if (k==4)
                    {
                        int sm=0;
                        for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i], req[C].a[i], req[D].a[i]});
                        ms.insert(sm);
                        if (ms.size()>c) ms.erase(ms.begin());
                        continue;
                    }
                    for (int E=D+1; E<sz; E++)
                    {
                        if (k==5)
                        {
                            int sm=0;
                            for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i], req[C].a[i], req[D].a[i], req[E].a[i]});
                            ms.insert(sm);
                            if (ms.size()>c) ms.erase(ms.begin());
                            continue;
                        }
                        for (int F=E+1; F<sz; F++)
                        {
                            int sm=0;
                            for (int i=0; i<k; i++) sm+=max({req[A].a[i], req[B].a[i], req[C].a[i], req[D].a[i], req[E].a[i], req[F].a[i]});
                            ms.insert(sm);
                            if (ms.size()>c) ms.erase(ms.begin());
                            continue;
                        }
                    }
                }
            }
        }
    }
    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

*/

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