oj.uz

답안 #942212

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942212 2024-03-10T11:06:42 Z phoenix0423 Olympiads (BOI19_olympiads) C++17
68 / 100
 1435 ms 220524 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{
        return ans < other.ans;
    }
};
priority_queue<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;
        }
    }
    // cout<<"ok\n";
    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.push(info(to_vector(st), cal(st)));
    int push = 1;
    for(int rd = 0; rd < c; rd++){
        auto [idx, ans] = q.top(); q.pop();
        if(rd == c - 1){
            cout<<ans<<"\n";
            return 0;
        }
        for(auto x : idx){
            if(push > 5e5) 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.push(info(to_vector(cur), cal(cur)));
                        used.insert(cur);
                    }
                    cur.erase(j);
                }
            }
        }
    }
}

Compilation message

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

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 507 ms 31568 KB Output is correct
2 Correct 500 ms 31552 KB Output is correct
3 Correct 573 ms 31432 KB Output is correct
4 Correct 498 ms 31672 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 395 ms 40908 KB Output is correct
2 Correct 379 ms 34032 KB Output is correct
3 Correct 413 ms 38904 KB Output is correct
4 Correct 398 ms 36644 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1271 ms 219596 KB Output is correct
2 Correct 1412 ms 219916 KB Output is correct
3 Correct 1245 ms 220028 KB Output is correct
4 Correct 1183 ms 219840 KB Output is correct
5 Correct 1409 ms 219760 KB Output is correct
6 Correct 127 ms 7880 KB Output is correct

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 507 ms 31568 KB Output is correct
2 Correct 500 ms 31552 KB Output is correct
3 Correct 573 ms 31432 KB Output is correct
4 Correct 498 ms 31672 KB Output is correct
5 Correct 395 ms 40908 KB Output is correct
6 Correct 379 ms 34032 KB Output is correct
7 Correct 413 ms 38904 KB Output is correct
8 Correct 398 ms 36644 KB Output is correct
9 Correct 1271 ms 219596 KB Output is correct
10 Correct 1412 ms 219916 KB Output is correct
11 Correct 1245 ms 220028 KB Output is correct
12 Correct 1183 ms 219840 KB Output is correct
13 Correct 1409 ms 219760 KB Output is correct
14 Correct 127 ms 7880 KB Output is correct
15 Incorrect 1435 ms 220524 KB Output isn't correct
16 Halted 0 ms 0 KB -