Submission #1098542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098542		simona1230	Olympiads (BOI19_olympiads)	C++17	100 / 100	74 ms	68488 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

int n,k,c;
int a[501][32];

vector<int> v[32];
struct team
{
    int used[501];
    int forb[501];
    int p[32];
    team()
    {
        for(int i=1; i<=n; i++)
            used[i]=forb[i]=0;
    }

    bool operator<(const team&t)const
    {
        int sum=0;
        for(int j=1; j<=k; j++)
        {
            int curr=v[j][t.p[j]];
            sum+=a[curr][j];
        }

        int sum2=0;
        for(int j=1; j<=k; j++)
        {
            int curr=v[j][p[j]];
            sum2+=a[curr][j];
        }
        return sum2<sum;
    }
};

priority_queue<team> q;

int h;
bool cmp(int i1,int i2)
{
    return a[i1][h]>a[i2][h];
}

void read()
{
    cin>>n>>k>>c;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=k; j++)
        {
            cin>>a[i][j];
            v[j].push_back(i);
        }
    }

    for(int i=1; i<=k; i++)
        h=i,sort(v[i].begin(),v[i].end(),cmp);
    for(int j=1; j<=k; j++)
        v[j].push_back(0);

    for(int i=1; i<=k; i++)
        for(int j=n; j>=1; j--)
            v[i][j]=v[i][j-1];
}


int comb[501][501];

void prec()
{
    for(int i=0; i<=n; i++)
    {
        for(int j=0; j<=i; j++)
        {
            if(i==0||j==0)comb[i][j]=1;
            else comb[i][j]=min(c,comb[i-1][j]+comb[i-1][j-1]);
            //cout<<i<<" "<<j<<" "<<comb[i][j]<<endl;
        }
    }
}

map<set<int>,int> mp;
void solve()
{
    team h;
    for(int i=1; i<=k; i++)
        h.p[i]=1,h.used[v[i][1]]=1;

    q.push(h);

    while(1)
    {
        team t=q.top();
        q.pop();

        int in=0,lf=0;
        for(int i=1; i<=n; i++)
            if(!t.used[i])
                lf++;

        set<int> s;
        for(int i=1; i<=k; i++)
            s.insert(v[i][t.p[i]]);

        mp[s]++;
        if(mp[s]>1)continue;

        in=s.size();
        c-=comb[lf][k-in];

        int sum=0;
        for(int d=1; d<=k; d++)
            sum+=a[v[d][t.p[d]]][d];

        //cout<<sum<<endl;
        if(c<=0)
        {
            cout<<sum<<endl;
            return;
        }

        for(auto it=s.begin(); it!=s.end(); it++)
        {
            team curr=t;
            int i=*it;
            curr.forb[i]=1;
            bool pos=1;
            for(int d=1; d<=k; d++)
            {
                while(curr.p[d]<=n&&curr.forb[v[d][curr.p[d]]])curr.p[d]++;
                if(curr.p[d]>n)pos=0;
                else curr.used[v[d][curr.p[d]]]=1;
            }

            if(pos)q.push(curr);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    prec();
    solve();

    return 0;
}
/*
9 2 7
1 4
8 3
10 3
3 2
7 5
6 9
3 7
2 4
9 3

*/

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