oj.uz

Submission #954619

# Submission time Handle Problem Language Result Execution time Memory
954619 2024-03-28T08:37:34 Z hengliao Olympiads (BOI19_olympiads) C++17
44 / 100
 794 ms 262144 KB 
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef int ll;

const ll inf=1e17;

struct team{
    vll v;
    ll n, id;

    void init(ll tn){
        n=tn;
        v=vll(n, -inf);
    }
    void rd(ll tn){
        n=tn;
        v.resize(n);
        for(ll i=0;i<n;i++){
            cin>>v[i];
        }
    }
    void mxwith(vll &cur){
        for(ll i=0;i<n;i++){
            cur[i]=max(cur[i], v[i]);
        }
    }

    void operator=(const team &tar){
        for(ll i=0;i<n;i++){
            v[i]=tar.v[i];
        }
        id=tar.id;
    }

    bool operator<(const team &tar) const{
        return id<tar.id;
    }
};

const ll mxN=505;

ll n, k, c;
vector<team> a;
vector<team> best;
bool use[mxN];

ll gt(vector<team> &tar, vll &cur){
    for(ll i=0;i<k;i++){
        tar[i].mxwith(cur);
    }
    ll re=0;
    for(ll i=0;i<k;i++){
        re+=cur[i];
    }
    return re;
}

ll gt2(vll &tar){
    ll re=0;
    for(ll i=0;i<k;i++){
        ll cur=0;
        for(ll j=0;j<k;j++){
            cur=max(cur, a[tar[j]].v[i]);
        }
        re+=cur;
    }
    return re;
}

void solve(){
    memset(use, 0, sizeof(use));
    cin>>n>>k>>c;
    a.resize(n);
    for(ll i=0;i<k;i++){
        team tep;
        tep.init(k);
        best.pb(tep);
    }
    for(ll i=0;i<n;i++){
        a[i].rd(k);
        a[i].id=i;
    }
    for(ll i=0;i<n;i++){
        for(ll j=0;j<k;j++){
            if(a[i].v[j]>best[j].v[j]){
                best[j]=a[i];
            }
        }
    }
    ll cnt=0;
    vector<team> be;
    for(ll i=0;i<k;i++){
        if(use[best[i].id]){
            cnt++;
        }
        else{
            use[best[i].id]=1;
            be.pb(best[i]);
        }
    }
    while(cnt--){
        for(ll i=0;i<n;i++){
            if(!use[i]){
                be.pb(a[i]);
                use[i]=1;
                break;
            }
        }
    }
    priority_queue<pair<ll, set<ll>>> pq;
    map<set<ll>, bool> done; 
    vll cur(k, -inf);
    ll re=gt(be, cur);
    set<ll> tep;
    for(ll i=0;i<n;i++){
        if(use[i]){
            tep.insert(i);
            //cout<<i<<' ';
        }
    }
    //cout<<'\n';
    //cout<<re<<'\n';
    pq.push({re, tep});
    done[tep]=1;
    ll ans;
    //assert(1);
    //bool b=0;
    for(ll i=0;i<c && !pq.empty();i++){
        pair<ll, set<ll>> now=pq.top(); pq.pop();
        ans=now.F;
        set<ll> tep=now.S;
        memset(use, 0, sizeof(use));
        for(auto it:tep){
            use[it]=1;
        }
        for(auto it:tep){
            set<ll> nxt;
            for(auto it2:tep){
                if(it2==it) continue;
                //assert(tep[j]<n);
                /*if(tep[j]>=n){
                    cout<<"bad "<<i<<'\n';
                    for(auto it:tep){
                        cout<<it<<' ';
                    }
                    cout<<'\n';
                    b=1;
                    break;
                }*/
                nxt.insert(it2);
            }
            //if(b) break;
            vll cur(k, -inf);
            for(auto it:nxt){
                for(ll j=0;j<k;j++){
                    cur[j]=max(cur[j], a[it].v[j]);
                }
            }
            for(ll j=0;j<n;j++){
                if(!use[j]){
                    nxt.insert(j);
                    if(done[nxt]){
                        nxt.erase(j);
                    }
                    else{
                        done[nxt]=1;
                        vll cur2=cur;
                        for(ll ii=0;ii<k;ii++){
                            cur2[ii]=max(cur2[ii], a[j].v[ii]);
                        }
                        ll re=0;
                        for(ll ii=0;ii<k;ii++){
                            re+=cur2[ii];
                        }
                        pq.push({re, nxt});
                        nxt.erase(j);
                    }
                    //done.insert(hs(nxt));
                }
            }
        }
    }
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

Compilation message

olympiads.cpp:13:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+17' to '2147483647' [-Woverflow]
   13 | const ll inf=1e17;
      |              ^~~~
olympiads.cpp: In function 'void solve()':
olympiads.cpp:191:16: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  191 |     cout<<ans<<'\n';
      |                ^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 42260 KB Output is correct
2 Correct 512 ms 42260 KB Output is correct
3 Correct 561 ms 42260 KB Output is correct
4 Correct 393 ms 10320 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 66324 KB Output is correct
2 Correct 376 ms 57108 KB Output is correct
3 Correct 413 ms 62740 KB Output is correct
4 Correct 429 ms 57172 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 794 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 42260 KB Output is correct
2 Correct 512 ms 42260 KB Output is correct
3 Correct 561 ms 42260 KB Output is correct
4 Correct 393 ms 10320 KB Output is correct
5 Correct 381 ms 66324 KB Output is correct
6 Correct 376 ms 57108 KB Output is correct
7 Correct 413 ms 62740 KB Output is correct
8 Correct 429 ms 57172 KB Output is correct
9 Runtime error 794 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -