Submission #1098466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098466		simona1230	Olympiads (BOI19_olympiads)	C++17	13 / 100	20 ms	10840 KiB

olympiads

#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[32][200048];
long long used[501][200048];
long long forb[501][200048];
long long calc[200048];
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];
        }
        //cout<<t.id<<" "<<id<<endl;
        calc[t.id]=sum;

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

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<<" "<<calc[id]<<endl;
        if(c<=0)
        {
            cout<<sum<<endl;
            return;
        }

        for(auto it=s.begin(); it!=s.end(); it++)
        {
            num++;
            long long i=*it;

            for(long long j=1; j<=n; j++)
                forb[j][num]=forb[j][id],
                used[j][num]=used[j][id],
                p[j][num]=p[j][id];
            forb[i][num]=1;

            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);
            else 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;
}
/*
17 6 1000
7022 83911 46765 31935 19446 66656
6121 97805 68364 82864 64495 31303
1 1 1 1 1 600000
49780 56291 79717 6555 84743 26406
4710 15679 81100 89945 83573 48055
1 1 1 600000 1 1
82101 91917 97516 94480 32826 10373
41005 85841 12650 2268 19268 46683
600000 1 1 1 1 1
1 600000 1 1 1 1
70630 60574 7183 52376 33888 58277
1 1 1 1 600000 1
20948 74095 92467 15797 42765 80995
1 1 600000 1 1 1
96223 13752 41056 8707 91053 30461
95774 7129 2053 70191 61664 91349
69095 21166 41032 23750 77365 98401

9 5 110
123 445 33 534 54
238 53 1432 2 34
10 32 438 543 6
3 232 3 140 76
237 545 5 85 123
634 9 241 112 65
33 734 326 523 124
235 422 595 867 71
935 793 154 325 657


40 6 2000
258843 114382 450217 223862 409101 139584
426719 409675 33602 334652 456390 144690
173925 102654 232891 403388 29161 127460
23743 252811 333412 4582 338188 449118
346811 376868 36087 52987 59932 30411
401868 382928 33105 414011 211397 191413
340666 496917 406359 203039 388314 149975
73493 391737 191800 306990 423413 152779
118795 1075 168608 419860 113219 473859
24658 423493 303063 185042 488421 339616
412410 360884 261748 192637 397214 155361
318606 469576 62371 311261 446074 306927
225007 371981 158777 87310 402339 366831
313060 396673 338864 429734 191529 119823
395484 102516 388925 183569 429577 201923
204257 216262 103782 7279 113556 433435
439291 332876 189239 2670 192208 422081
477280 412700 19751 113640 226480 388501
157258 127729 447800 272534 93426 289978
181376 61606 429918 408216 121819 431402
295136 12977 437588 107012 274979 262204
373882 186456 264765 153112 95103 495726
408813 498870 313711 394829 68651 26737
155445 268723 75002 15736 288157 208108
164412 320804 349936 409217 101905 183709
199980 26426 7831 255827 445027 301085
96035 249043 293013 304966 183586 410031
380921 483976 184320 63726 114403 80139
415263 483220 261904 366320 95350 163289
87831 161183 67223 389600 178231 320302
225389 146366 360261 130059 220825 87203
121396 365406 118550 280405 189790 267476
419067 312065 85957 353007 228889 117148
409946 150624 85008 92243 467987 208538
162146 371950 145210 185868 242041 58810
280022 139123 455685 156624 481984 395518
8767 228209 280678 364658 485101 421353
194894 311943 89494 324790 101041 108634
83428 32192 133690 59197 314690 380340
482621 98776 414232 369042 417264 52626

*/

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