oj.uz

Submission #942232

# Submission time Handle Problem Language Result Execution time Memory
942232 2024-03-10T11:25:33 Z phoenix0423 Olympiads (BOI19_olympiads) C++17
68 / 100
 854 ms 41312 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++){
        set<info> nw;
        for(auto x : q){
            nw.insert(x);
            if(nw.size() >= c - rd) break;
        }
        swap(nw, q);
        auto [idx, ans] = *q.begin(); q.erase(q.begin());
        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:75:26: warning: comparison of integer expressions of different signedness: 'std::set<info>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |             if(nw.size() >= c - rd) break;
      |                ~~~~~~~~~~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 20260 KB Output is correct
2 Correct 802 ms 20172 KB Output is correct
3 Correct 597 ms 20304 KB Output is correct
4 Correct 509 ms 20252 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 854 ms 34944 KB Output is correct
2 Correct 818 ms 29528 KB Output is correct
3 Correct 816 ms 33660 KB Output is correct
4 Correct 844 ms 30804 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 41296 KB Output is correct
2 Correct 733 ms 41312 KB Output is correct
3 Correct 695 ms 41216 KB Output is correct
4 Correct 640 ms 41292 KB Output is correct
5 Correct 670 ms 41296 KB Output is correct
6 Correct 572 ms 7452 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 20260 KB Output is correct
2 Correct 802 ms 20172 KB Output is correct
3 Correct 597 ms 20304 KB Output is correct
4 Correct 509 ms 20252 KB Output is correct
5 Correct 854 ms 34944 KB Output is correct
6 Correct 818 ms 29528 KB Output is correct
7 Correct 816 ms 33660 KB Output is correct
8 Correct 844 ms 30804 KB Output is correct
9 Correct 786 ms 41296 KB Output is correct
10 Correct 733 ms 41312 KB Output is correct
11 Correct 695 ms 41216 KB Output is correct
12 Correct 640 ms 41292 KB Output is correct
13 Correct 670 ms 41296 KB Output is correct
14 Correct 572 ms 7452 KB Output is correct
15 Incorrect 676 ms 41040 KB Output isn't correct
16 Halted 0 ms 0 KB -