oj.uz

Submission #1098541

# Submission time Handle Problem Language Result Execution time Memory
1098541 2024-10-09T13:50:17 Z simona1230 Olympiads (BOI19_olympiads) C++17
100 / 100
 55 ms 68508 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;
        }

        team nxt;
        bool nun=1;
        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(nun&&pos||pos&&nxt<curr)
            {
                nxt=curr;
                nun=0;
            }
            if(pos)
            q.push(curr);
        }
        if(!nun);
    }
}

void slow()
{
    vector<int> ans;

    if(k==2)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                int sum=0;
                for(int d=1; d<=k; d++)
                    sum+=max(a[i][d],a[j][d]);
                ans.push_back(sum);
            }
        }
    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            int sum=0;
            for(int d=1; d<=k; d++)
                sum+=a[i][d];
            ans.push_back(sum);
        }

    }
    sort(ans.begin(),ans.end());
    cout<<ans[ans.size()-c]<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    read();
    if(k<=2)slow();
    else
    {
        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

*/

Compilation message

olympiads.cpp: In function 'void solve()':
olympiads.cpp:141:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  141 |             if(nun&&pos||pos&&nxt<curr)
      |                ~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 984 KB Output is correct
2 Correct 6 ms 1004 KB Output is correct
3 Correct 4 ms 988 KB Output is correct
4 Correct 2 ms 988 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4796 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 33 ms 33900 KB Output is correct
4 Correct 32 ms 34076 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18308 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 55 ms 68456 KB Output is correct
4 Correct 55 ms 68508 KB Output is correct
5 Correct 14 ms 18308 KB Output is correct
6 Correct 9 ms 8880 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 984 KB Output is correct
2 Correct 6 ms 1004 KB Output is correct
3 Correct 4 ms 988 KB Output is correct
4 Correct 2 ms 988 KB Output is correct
5 Correct 6 ms 4796 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 33 ms 33900 KB Output is correct
8 Correct 32 ms 34076 KB Output is correct
9 Correct 13 ms 18308 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 55 ms 68456 KB Output is correct
12 Correct 55 ms 68508 KB Output is correct
13 Correct 14 ms 18308 KB Output is correct
14 Correct 9 ms 8880 KB Output is correct
15 Correct 49 ms 35164 KB Output is correct
16 Correct 16 ms 18308 KB Output is correct
17 Correct 54 ms 68364 KB Output is correct
18 Correct 44 ms 35112 KB Output is correct
19 Correct 1 ms 1368 KB Output is correct