Submission #942283

#	Time	Username	Problem	Language	Result	Execution time	Memory
942283		phoenix0423	Olympiads (BOI19_olympiads)	C++17	100 / 100	174 ms	28044 KiB

olympiads

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int INF = 1e9 + 7;
int a[505][10], ord[10][505], pos[10][505];
int n, k, c;

struct info{
    vector<int> idx;
    int ans;
    info(){}
    info(vector<int> _idx, int _ans) : idx(_idx), ans(_ans){}
    bool operator < (const info& other) const{
        return ans < other.ans;
    }
};

set<set<int>> used;
int cal(set<int> id){
    vector<int> mx(k);
    for(auto x : id){
        for(int i = 0; i < k; i++){
            mx[i] = max(mx[i], a[x][i]);
        }
    }
    return accumulate(mx.begin(), mx.end(), 0);
}
set<int> to_set(vector<int> a){
    set<int> st;
    for(auto x : a) st.insert(x);
    return st;
}
vector<int> to_vector(set<int> st){
    vector<int> a;
    for(auto x : st) a.pb(x);
    return a;
}
signed main(void){
    fastio;
    cin>>n>>k>>c;
    vector<int> mx(k);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < k; j++) cin>>a[i][j];
    }
    for(int j = 0; j < k; j++){
        for(int i = 0; i < n; i++) ord[j][i] = i;
        sort(ord[j], ord[j] + n, [&](int x, int y){ return a[x][j] > a[y][j];});
        for(int i = 0; i < n; i++) pos[j][ord[j][i]] = i;
    }
    set<int> st;
    for(int i = 0; i < k; i++) st.insert(ord[i][0]);
    for(int i = 0; i < n; i++){
        if(st.size() == k) break;
        st.insert(i);
    }
    priority_queue<info> q;
    q.push(info(to_vector(st), cal(st)));
    used.insert(st);
    for(int rd = 0; rd < c; rd++){
        auto [id, val] = q.top(); q.pop();
        if(rd == c - 1){
            cout<<val<<"\n";
            return 0;
        }
        for(int i = 0; i < k; i++){
            set<int> cur;
            for(int j = 0; j < k; j++) if(i != j) cur.insert(id[j]);
            for(int j = 0; j < k; j++){
                if(pos[j][id[i]] == n - 1) continue;
                cur.insert(ord[j][pos[j][id[i]] + 1]);
                if(cur.size() == k && !used.count(cur)){
                    used.insert(cur);
                    q.push(info(to_vector(cur), cal(cur)));
                }
                if(cur.size() == k) cur.erase(ord[j][pos[j][id[i]] + 1]);
            }
        }
    }
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:62:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |         if(st.size() == k) break;
      |            ~~~~~~~~~~^~~~
olympiads.cpp:80:31: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |                 if(cur.size() == k && !used.count(cur)){
      |                    ~~~~~~~~~~~^~~~
olympiads.cpp:84:31: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |                 if(cur.size() == k) cur.erase(ord[j][pos[j][id[i]] + 1]);
      |                    ~~~~~~~~~~~^~~~

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