oj.uz

Submission #942222

# Submission time Handle Problem Language Result Execution time Memory
942222 2024-03-10T11:21:29 Z phoenix0423 Olympiads (BOI19_olympiads) C++17
68 / 100
 414 ms 40852 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];
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{
        if(ans != other.ans) return ans > other.ans;
        else{
            for(int i = 0; i < k; i++) if(idx[i] != other.idx[i]) return idx[i] < other.idx[i];
        }
        return false;
    }
};
set<info> q;
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];
            if(a[i][j] > a[mx[j]][j]) mx[j] = i;
        }
    }
    set<int> st;
    for(int i = 0; i < k; i++) st.insert(mx[i]);
    for(int i = 0; i < n; i++){
        if(st.size() == k) break;
        if(st.count(i)) continue;
        st.insert(i);
    }
    used.insert(st);
    q.insert(info(to_vector(st), cal(st)));
    int push = 0;
    for(int rd = 0; rd < c; rd++){
        auto [idx, ans] = *q.begin(); q.erase(q.begin());
        while(q.size() > c) q.erase(--q.end());
        if(rd == c - 1){
            cout<<ans<<"\n";
            return 0;
        }
        for(auto x : idx){
            if(push > 1e5) break;
            set<int> cur;
            for(auto u : idx){
                if(u != x) cur.insert(u);
            }
            for(int j = 0; j < n; j++){
                if(!cur.count(j)){
                    cur.insert(j);
                    if(!used.count(cur)){
                        push++;
                        q.insert(info(to_vector(cur), cal(cur)));
                        used.insert(cur);
                    }
                    cur.erase(j);
                }
            }
        }
    }
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:64:22: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |         if(st.size() == k) break;
      |            ~~~~~~~~~~^~~~
olympiads.cpp:73:24: warning: comparison of integer expressions of different signedness: 'std::set<info>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |         while(q.size() > c) q.erase(--q.end());
      |               ~~~~~~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 19804 KB Output is correct
2 Correct 394 ms 19864 KB Output is correct
3 Correct 212 ms 20544 KB Output is correct
4 Correct 123 ms 19796 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 34900 KB Output is correct
2 Correct 355 ms 29668 KB Output is correct
3 Correct 414 ms 33364 KB Output is correct
4 Correct 384 ms 30548 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 40784 KB Output is correct
2 Correct 300 ms 40852 KB Output is correct
3 Correct 236 ms 40788 KB Output is correct
4 Correct 220 ms 40776 KB Output is correct
5 Correct 246 ms 40536 KB Output is correct
6 Correct 125 ms 7256 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 19804 KB Output is correct
2 Correct 394 ms 19864 KB Output is correct
3 Correct 212 ms 20544 KB Output is correct
4 Correct 123 ms 19796 KB Output is correct
5 Correct 379 ms 34900 KB Output is correct
6 Correct 355 ms 29668 KB Output is correct
7 Correct 414 ms 33364 KB Output is correct
8 Correct 384 ms 30548 KB Output is correct
9 Correct 273 ms 40784 KB Output is correct
10 Correct 300 ms 40852 KB Output is correct
11 Correct 236 ms 40788 KB Output is correct
12 Correct 220 ms 40776 KB Output is correct
13 Correct 246 ms 40536 KB Output is correct
14 Correct 125 ms 7256 KB Output is correct
15 Incorrect 248 ms 40568 KB Output isn't correct
16 Halted 0 ms 0 KB -