oj.uz

Submission #1098437

# Submission time Handle Problem Language Result Execution time Memory
1098437 2024-10-09T11:41:25 Z simona1230 Olympiads (BOI19_olympiads) C++17
13 / 100
 125 ms 21892 KB 
#include <bits/stdc++.h>

using namespace std;

long long n,k,c;
long long a[2048][2048];

vector<long long> v[2048];
long long p[2048][2048];
long long used[2048][2048];
long long forb[2048][2048];
struct team
{
    long long id;
    team() {}
    team(long long i)
    {
        id=i;
    }

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

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

priority_queue<team> q;

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

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

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

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

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

    /*for(long long i=1; i<=k; i++)
    {
        for(long long j=1; j<=n; j++)
            cout<<v[i][j]<<" ";
        cout<<endl;
    }*/
}


long long comb[2048][2048];

void prec()
{
    for(long long i=0; i<=n; i++)
    {
        for(long long j=0; j<=i; j++)
        {
            if(i==0||j==0||i==j)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<long long>,long long> mp;
long long num=0;
void solve()
{
    num++;
    for(long long i=1; i<=k; i++)
        p[i][num]=1,used[v[i][1]][num]=1;

    q.push(num);
    while(1)
    {
        long long id=q.top().id;
        q.pop();

        long long in=0,lf=0;
        for(long long i=1; i<=n; i++)
            if(!used[i][id])
            {
                lf++;
            }

        set<long long> s;
        for(long long i=1; i<=k; i++)
            s.insert(v[i][p[i][id]]);
        mp[s]++;
        if(mp[s]>1)continue;

        in=s.size();

        c-=comb[lf][k-in];
        long long sum=0;
        for(long long d=1; d<=k; d++)
        {
            sum+=a[v[d][p[d][id]]][d];
            //cout<<v[d][p[d][id]]<<" "<<d<<endl;
        }
        //cout<<sum<<endl;
        if(c<=0)
        {
            cout<<sum<<endl;
            return;
        }

        for(auto it=s.begin(); it!=s.end(); it++)
        {
            num++;
            long long i=*it;
            forb[i][num]=1;
            for(long long j=1; j<=n; j++)
                forb[j][num]=max(forb[j][num],forb[j][id]),
                             used[j][num]=used[j][id];
            bool pos=1;
            for(long long d=1; d<=k; d++)
            {
                while(p[d][num]<=n&&forb[v[d][p[d][num]]][num])p[d][num]++;
                if(p[d][num]>n)pos=0;
                else used[v[d][p[d][num]]][num]=1;
            }

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

void slow()
{
    vector<long long> ans;

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

    }
    else if(k==2)
    {
        for(long long i=1; i<=n; i++)
        {
            for(long long j=i+1; j<=n; j++)
            {
                long long sum=0;
                for(long long d=1; d<=k; d++)
                    sum+=max(a[i][d],a[j][d]);
                ans.push_back(sum);
            }
        }
    }
    else
    {
        for(long long i=1; i<=n; i++)
        {
            long long sum=0;
            for(long long 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<=3)slow();
    else
    {
        prec();
        solve();
    }
    return 0;
}
/*
9 4 120
1 4 3 4
8 3 1 2
10 3 8 5
3 2 3 10
7 5 5 8
6 9 2 1
3 7 6 5
2 4 9 8
9 3 1 3

*/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3544 KB Output is correct
2 Correct 7 ms 3548 KB Output is correct
3 Correct 6 ms 3548 KB Output is correct
4 Correct 4 ms 3544 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2140 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Incorrect 7 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 21588 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Incorrect 125 ms 21892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3544 KB Output is correct
2 Correct 7 ms 3548 KB Output is correct
3 Correct 6 ms 3548 KB Output is correct
4 Correct 4 ms 3544 KB Output is correct
5 Correct 4 ms 2140 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Incorrect 7 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -