oj.uz

Submission #1098542

# Submission time Handle Problem Language Result Execution time Memory
1098542 2024-10-09T13:51:39 Z simona1230 Olympiads (BOI19_olympiads) C++17
100 / 100
 74 ms 68488 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2260 KB Output is correct
2 Correct 8 ms 2768 KB Output is correct
3 Correct 5 ms 2632 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4800 KB Output is correct
2 Correct 2 ms 2628 KB Output is correct
3 Correct 33 ms 33988 KB Output is correct
4 Correct 35 ms 34084 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18304 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 74 ms 68488 KB Output is correct
4 Correct 63 ms 68420 KB Output is correct
5 Correct 16 ms 18304 KB Output is correct
6 Correct 9 ms 8884 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2260 KB Output is correct
2 Correct 8 ms 2768 KB Output is correct
3 Correct 5 ms 2632 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 7 ms 4800 KB Output is correct
6 Correct 2 ms 2628 KB Output is correct
7 Correct 33 ms 33988 KB Output is correct
8 Correct 35 ms 34084 KB Output is correct
9 Correct 15 ms 18304 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 74 ms 68488 KB Output is correct
12 Correct 63 ms 68420 KB Output is correct
13 Correct 16 ms 18304 KB Output is correct
14 Correct 9 ms 8884 KB Output is correct
15 Correct 54 ms 35352 KB Output is correct
16 Correct 17 ms 18144 KB Output is correct
17 Correct 60 ms 68272 KB Output is correct
18 Correct 48 ms 34992 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct