Submission #866528

#	Time	Username	Problem	Language	Result	Execution time	Memory
866528		mychecksedad	Olympiads (BOI19_olympiads)	C++17	0 / 100	859 ms	262144 KiB

olympiads

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

int n, k, c;
vector<vector<int>> v;
vector<int> check(vector<int> &x, vector<int> &y){
  vector<int> aa;
  merge(all(x), all(y), back_inserter(aa));
  aa.erase(unique(all(aa)), aa.end());
  return aa;
}
void solve(){
  cin >> n >> k >> c;
  v.resize(n, vector<int> (k));
  for(int i = 0; i < n; ++i) for(auto &x: v[i]) cin >> x;
  if(k == 1){
    int ans = 0;
    for(int i = 0; i < n; ++i) ans = max(ans, v[i][0]);
    cout << ans;
  }else if(k == 2){
    int ans = 0;
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        ans = max(ans, v[i][0] + v[j][1]);
      }
    }
    cout << ans;
  }else{
    vector<pair<int, vector<int>>> A;
    for(int i = 0; i < n; ++i){
      for(int j = i + 1; j < n; ++j){
        for(int l = j + 1; l < n; ++l){
          vector<int> mx(k), tt;
          for(int kk = 0; kk < k; ++kk){
            mx[kk] = max({v[i][kk], v[j][kk], v[l][kk]});
          }
          for(int u = 0; u < k; ++u) tt.pb(mx[u]);
          sort(all(tt), greater<int>());
          A.pb({tt[0] + tt[1] + tt[2], {i, j, l}});
        }
      }
    }
    sort(all(A), [&](const pair<int, vector<int>> &x, const pair<int, vector<int>> &y){
      return x.first < y.first;
    });
    if(k == 3){
      cout << A[0].first;
      return;
    }
    set<pair<int, vector<int>>> S;
    for(int i = 0; S.size() < 4*c && i < A.size(); ++i){
      for(int j = i + 1; j < A.size(); ++j){
        auto x = check(A[i].second, A[j].second);
        if(int(x.size()) == k){
          int res = 0;
          for(int kk = 0; kk < k; ++kk){
            int mx = 0;
            for(int l: A[i].second) mx = max(mx, v[l][kk]);
            for(int l: A[j].second) mx = max(mx, v[l][kk]);
            res += mx;
          }
          S.insert({res, x});
        }
      }
    }
    int cc = 1;
    auto it = prev(S.end());
    while(cc < c){
      --it;
      cc++;
    }
    cout << (*it).first;
  }
}

int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

olympiads.cpp: In function 'void solve()':
olympiads.cpp:59:29: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |     for(int i = 0; S.size() < 4*c && i < A.size(); ++i){
      |                    ~~~~~~~~~^~~~~
olympiads.cpp:59:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; S.size() < 4*c && i < A.size(); ++i){
      |                                      ~~^~~~~~~~~~
olympiads.cpp:60:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |       for(int j = i + 1; j < A.size(); ++j){
      |                          ~~^~~~~~~~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:86:15: warning: unused variable 'aa' [-Wunused-variable]
   86 |   int tt = 1, aa;
      |               ^~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32