oj.uz

Submission #942235

# Submission time Handle Problem Language Result Execution time Memory
942235 2024-03-10T11:26:37 Z phoenix0423 Olympiads (BOI19_olympiads) C++17
44 / 100
 2000 ms 212048 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;
      |                ~~~~~~~~~~^~~~~~~~~
olympiads.cpp:70:9: warning: unused variable 'push' [-Wunused-variable]
   70 |     int push = 0;
      |         ^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 24900 KB Output is correct
2 Correct 982 ms 24956 KB Output is correct
3 Correct 1108 ms 24980 KB Output is correct
4 Correct 944 ms 24832 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 35176 KB Output is correct
2 Correct 814 ms 29480 KB Output is correct
3 Correct 827 ms 33244 KB Output is correct
4 Correct 861 ms 30548 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 212048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 24900 KB Output is correct
2 Correct 982 ms 24956 KB Output is correct
3 Correct 1108 ms 24980 KB Output is correct
4 Correct 944 ms 24832 KB Output is correct
5 Correct 827 ms 35176 KB Output is correct
6 Correct 814 ms 29480 KB Output is correct
7 Correct 827 ms 33244 KB Output is correct
8 Correct 861 ms 30548 KB Output is correct
9 Execution timed out 2068 ms 212048 KB Time limit exceeded
10 Halted 0 ms 0 KB -