Submission #494680

#	Time	Username	Problem	Language	Result	Execution time	Memory
494680		wiwiho	Olympiads (BOI19_olympiads)	C++14	13 / 100	11 ms	812 KiB

olympiads

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

struct discr{
    vector<int> t;
    int sz;
    discr(vector<int>& v): t(v){
        gsort(t);
        uni(t);
        sz = t.size();
    }
    int operator()(int x){
        return lower_bound(iter(t), x, greater<>()) - t.begin();
    }
    int operator[](int x){
        return t[x];
    }
};

int n, k, c;
vector<discr> d;
vector<int> ok;
vector<vector<int>> ex;
vector<vector<int>> a;
int cnt = 0;
vector<int> mx;
vector<bool> use;

void init(){
    a.resize(n + 1, vector<int>(k));
    mx.resize(k);
    use.resize(n + 1);
    ex.resize(k);
}

struct info{
    vector<int> v;
    int sum = 0;
    info(vector<int> v): v(v){
        for(int i = 0; i < k; i++) sum += d[i][v[i]];
    }
    bool operator<(const info& b) const{
        return sum == b.sum ? v < b.v : sum > b.sum;
    }
};

vector<int> arr;
set<vector<int>> owo;
void dfs(int now, vector<int>& v){
    if(now == k){
        for(int i = 0; i < k; i++){
            assert(mx[i] == d[i][v[i]]);
        }
        vector<int> tv = arr;
        lsort(tv);
        //cerr << "try ";
        //printv(arr, cerr);
        //for(auto i : owo) printv(i, cerr);
        if(owo.find(tv) != owo.end()) return;
        owo.insert(tv);
        //cerr << "ok ";
        //printv(arr, cerr);
        cnt++;
        if(cnt == c){
            int sum = 0;
            for(int i = 0; i < k; i++) sum += mx[i];
            cout << sum << "\n";
            exit(0);
        }
        return;
    }
    
    if(mx[now] == d[now][v[now]]){
        for(int i : ok){
            if(use[i]) continue;
            vector<int> omx = mx;
            for(int t = 0; t < k; t++) mx[t] = max(mx[t], a[i][t]);
            use[i] = true;
            arr.eb(i);
            dfs(now + 1, v);
            arr.pob;
            use[i] = false;
            mx = omx;
        }
    }
    else{
        for(int i : ex[now]){
            if(use[i]) continue;
            vector<int> omx = mx;
            for(int t = 0; t < k; t++) mx[t] = max(mx[t], a[i][t]);
            use[i] = true;
            arr.eb(i);
            dfs(now + 1, v);
            arr.pob;
            use[i] = false;
            mx = omx;
        }
    }
}

int main(){
    StarBurstStream

    cin >> n >> k >> c;
    init();

    vector<vector<int>> td(k);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < k; j++){
            cin >> a[i][j];
            td[j].eb(a[i][j]);
        }
    }
    for(int i = 0; i < k; i++){
        d.eb(td[i]);
    }

    /*cerr << "discr\n";
    for(int i = 0; i < k; i++){
        cerr << i << "  ";
        printv(d[i].t, cerr);
    }*/

    set<info> pq;
    set<info> vst;
    pq.insert(info(vector<int>(k)));
    vst.insert(info(vector<int>(k)));
    
    while(!pq.empty()){
        info vi = *pq.begin();
        pq.erase(pq.begin());
        vector<int> v = vi.v;
        
        for(int i = 0; i < k; i++) ex[i].clear();
        ok.clear();
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < k; j++){
                if(a[i][j] > d[j][v[j]]) goto nxt;
            }
            ok.eb(i);
            for(int j = 0; j < k; j++){
                if(a[i][j] == d[j][v[j]]) ex[j].eb(i);
            }
            nxt:;
        }
        bool oao = false;
        for(int i = 0; i < k; i++) if(ex[i].empty()) oao = true;
        if(ok.size() < k) continue;

        if(!oao){
            //cerr << "solve ";
            //printv(v, cerr);
            //printv(ok, cerr);

            fill(iter(mx), -1);
            dfs(0, v);
        }

        for(int i = 0; i < k; i++){
            if(v[i] + 1 >= d[i].sz) continue;
            v[i]++;
            info t = v;
            if(vst.find(t) != vst.end()) continue;
            vst.insert(t);
            pq.insert(t);
            v[i]--;
        }
    }
    //assert(false);

    return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:207:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  207 |         if(ok.size() < k) continue;
      |            ~~~~~~~~~~^~~

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