제출 #1338577

#제출 시각아이디문제언어결과실행 시간메모리
1338577loomOlympiads (BOI19_olympiads)C++20
100 / 100
55 ms20772 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define _ <<' '<<
#define nl '\n'

int n, k, c;
int a[500][6];

struct st{
   vector<int> tm, ex;
   int in = 0;

   st(int n, int k){
      tm.resize(k);
      ex.resize(n);
      make();
   }

   bool operator < (const st& st2) const {
      return sum() < st2.sum();
   }

   int sum() const {
      int s = 0;

      for(int j = 0; j < k; j++){
         int mx = 0;

         for(int i : tm){
            mx = max(mx, a[i][j]);
         }

         s += mx;
      }

      return s;
   }

   int make(){
      for(int j = in; j < k; j++){
         int mx = -1;

         for(int i = 0; i < n; i++){
            if(count(tm.begin(), tm.begin()+j, i) or ex[i]) continue;

            if(mx < a[i][j]){
               mx = a[i][j];
               tm[j] = i;
            }
         }

         if(mx == -1) return 0;
      }

      return 1;
   }

   vector<st> next(){
      vector<st> v;

      for(int i = in; i < k; i++){
         st nxt = *this;
         nxt.ex[tm[i]] = 1;
         nxt.in = i;

         if(nxt.make()) v.push_back(nxt);
      }

      return v;
   }
};

void solve(){
   cin>>n>>k>>c;

   for(int i = 0; i < n; i++){
      for(int j = 0; j < k; j++){
         cin>>a[i][j];
      }
   }

   st mx(n, k);
   
   priority_queue<st> pq;
   pq.push(mx);

   for(int i = 0; i < c-1; i++){
      mx = pq.top(); 
      pq.pop();

      auto v = mx.next();

      for(st nxt : v){
         pq.push(nxt);
      }
   }

   cout<<pq.top().sum();
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...