oj.uz

Submission #388269

# Submission time Handle Problem Language Result Execution time Memory
388269 2021-04-10T17:39:48 Z leaked Olympiads (BOI19_olympiads) C++14
100 / 100
 90 ms 14872 KB 
#include <bits/stdc++.h>
//#pra
#define sz(x) (int)x.size()
#define vec vector
#define pb push_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int N=5e2+3;
typedef unsigned long long ull;
auto rnd=bind(uniform_int_distribution<long long>(1,1e18),mt19937(time(0)));
ull r[N];
int a[N][6];
int k;
int func(const array<int,6> &vc){
    int s=0;
    for(int i=0;i<k;i++){
        int mx=0;
        for(int j=0;j<k;j++){
            mx=max(mx,a[vc[j]][i]);
        }
        s+=mx;
    }
    return s;
};
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    ifstream cin("input.txt");
    int n,c;
    cin>>n>>k>>c;
//    vec<vec<int>>a(n,vec<int>(k));
    vec<vec<int>>p(k,vec<int>(n)),obr(n,vec<int>(k));
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            cin>>a[i][j];
        }
//        cerr<<i<<endl;
    }
    for(int i=0;i<k;i++){
        auto cmp=[&](int x,int y){
            return a[x][i]>a[y][i];
        };
        iota(all(p[i]),0);
        sort(all(p[i]),cmp);
        for(int j=0;j<n;j++){
            obr[p[i][j]][i]=j;
        }
    }
    priority_queue<pair<int,array<int,6>>>pq;
    /// to push;

    {
        set<int>st;
        for(int i=0;i<k;i++) st.insert(p[i][0]);
        for(int i=0;i<n;i++){
            if(sz(st)<k) st.insert(i);
        }
        array<int,6>lel;
        for(int i=0;i<k;i++){
            lel[i]=*st.begin();
            st.erase(st.begin());
        }
        pq.push({func(lel),lel});
    }
    for(int i=0;i<n;i++) r[i]=rnd();
    map<ull,int>mp;
    while(!pq.empty()){
        auto v=pq.top();pq.pop();
        ull hs=0;
        for(int i=0;i<k;i++){
            hs^=r[v.s[i]];
        }
        if(mp.count(hs)) continue;
        mp[hs]=1;
        c--;
//        cerr<<v.f<<endl;
        if(c==0){
            cout<<v.f<<endl;
            return 0;
        }
        auto arr=v.s;
        for(int chng=0;chng<k;chng++){
            for(int w=0;w<k;w++){
                for(int j=0;j<k;j++){
                    if(obr[arr[w]][j]==n-1) continue;
                    int nw=p[j][obr[arr[w]][j]+1];
                    bool ok=1;
                    for(int t=0;t<k;t++){
                        if(t!=chng && arr[t]==nw) ok=0;
                    }
                    if(ok){
                        int prv=arr[chng];
                        arr[chng]=nw;
                        pq.push({func(arr),arr});
                        arr[chng]=prv;
                    }
                }
            }
        }
    }
    assert(false);
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 932 KB Output is correct
2 Correct 4 ms 920 KB Output is correct
3 Correct 5 ms 932 KB Output is correct
4 Correct 5 ms 716 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 14772 KB Output is correct
2 Correct 90 ms 7604 KB Output is correct
3 Correct 68 ms 7604 KB Output is correct
4 Correct 72 ms 7564 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 14816 KB Output is correct
2 Correct 65 ms 7624 KB Output is correct
3 Correct 66 ms 14760 KB Output is correct
4 Correct 68 ms 14804 KB Output is correct
5 Correct 79 ms 14832 KB Output is correct
6 Correct 88 ms 7520 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 932 KB Output is correct
2 Correct 4 ms 920 KB Output is correct
3 Correct 5 ms 932 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 81 ms 14772 KB Output is correct
6 Correct 90 ms 7604 KB Output is correct
7 Correct 68 ms 7604 KB Output is correct
8 Correct 72 ms 7564 KB Output is correct
9 Correct 73 ms 14816 KB Output is correct
10 Correct 65 ms 7624 KB Output is correct
11 Correct 66 ms 14760 KB Output is correct
12 Correct 68 ms 14804 KB Output is correct
13 Correct 79 ms 14832 KB Output is correct
14 Correct 88 ms 7520 KB Output is correct
15 Correct 66 ms 14804 KB Output is correct
16 Correct 79 ms 14872 KB Output is correct
17 Correct 53 ms 4028 KB Output is correct
18 Correct 55 ms 7596 KB Output is correct
19 Correct 66 ms 7652 KB Output is correct