oj.uz

Submission #942283

# Submission time Handle Problem Language Result Execution time Memory
942283 2024-03-10T11:59:24 Z phoenix0423 Olympiads (BOI19_olympiads) C++17
100 / 100
 174 ms 28044 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1628 KB Output is correct
2 Correct 8 ms 1748 KB Output is correct
3 Correct 6 ms 1628 KB Output is correct
4 Correct 3 ms 860 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 16368 KB Output is correct
2 Correct 84 ms 13252 KB Output is correct
3 Correct 44 ms 5968 KB Output is correct
4 Correct 53 ms 6860 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 26980 KB Output is correct
2 Correct 35 ms 3156 KB Output is correct
3 Correct 143 ms 24888 KB Output is correct
4 Correct 152 ms 26432 KB Output is correct
5 Correct 66 ms 9168 KB Output is correct
6 Correct 47 ms 5340 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1628 KB Output is correct
2 Correct 8 ms 1748 KB Output is correct
3 Correct 6 ms 1628 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 100 ms 16368 KB Output is correct
6 Correct 84 ms 13252 KB Output is correct
7 Correct 44 ms 5968 KB Output is correct
8 Correct 53 ms 6860 KB Output is correct
9 Correct 157 ms 26980 KB Output is correct
10 Correct 35 ms 3156 KB Output is correct
11 Correct 143 ms 24888 KB Output is correct
12 Correct 152 ms 26432 KB Output is correct
13 Correct 66 ms 9168 KB Output is correct
14 Correct 47 ms 5340 KB Output is correct
15 Correct 174 ms 28044 KB Output is correct
16 Correct 170 ms 27068 KB Output is correct
17 Correct 52 ms 5880 KB Output is correct
18 Correct 71 ms 11300 KB Output is correct
19 Correct 35 ms 3152 KB Output is correct