oj.uz

Submission #866537

# Submission time Handle Problem Language Result Execution time Memory
866537 2023-10-26T10:38:29 Z mychecksedad Olympiads (BOI19_olympiads) C++17
13 / 100
 2000 ms 109892 KB 
/* 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;
    vector<int> cc;
    for(int i = 0; i < n; ++i) cc.pb(v[i][0]);
    sort(all(cc), greater<int>());
    cout << cc[c-1];
  }else if(k == 2){
    int ans = 0;
    vector<int> cc;
    for(int i = 0; i < n; ++i){
      for(int j = i+1; j < n; ++j){
        cc.pb(max(v[i][0], v[j][0])+max(v[i][1], v[j][1]));
      }
    }
    sort(all(cc), greater<int>());
    cout << cc[c-1];
  }else{
    set<pair<int, vector<int>>> B;
    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>());
          B.insert({tt[0] + tt[1] + tt[2], {i, j, l}});
          if(B.size() > 1000000) B.erase(B.begin());
        }
      }
    }
    vector<pair<int, vector<int>>> A;
    for(auto x: B) A.pb(x);
    if(k == 3){
      cout << A[c-1].first;
      return;
    }
    set<pair<int, vector<int>>> S;
    for(int i = 0; S.size() < 10*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

olympiads.cpp: In function 'void solve()':
olympiads.cpp:25:9: warning: unused variable 'ans' [-Wunused-variable]
   25 |     int ans = 0;
      |         ^~~
olympiads.cpp:31:9: warning: unused variable 'ans' [-Wunused-variable]
   31 |     int ans = 0;
      |         ^~~
olympiads.cpp:63: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]
   63 |     for(int i = 0; S.size() < 10*c && i < A.size(); ++i){
      |                    ~~~~~~~~~^~~~~~
olympiads.cpp:63:41: 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]
   63 |     for(int i = 0; S.size() < 10*c && i < A.size(); ++i){
      |                                       ~~^~~~~~~~~~
olympiads.cpp:64: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]
   64 |       for(int j = i + 1; j < A.size(); ++j){
      |                          ~~^~~~~~~~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:90:15: warning: unused variable 'aa' [-Wunused-variable]
   90 |   int tt = 1, aa;
      |               ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 988 KB Output is correct
2 Correct 6 ms 988 KB Output is correct
3 Correct 5 ms 988 KB Output is correct
4 Correct 2 ms 988 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 988 KB Output is correct
2 Correct 6 ms 988 KB Output is correct
3 Correct 5 ms 988 KB Output is correct
4 Correct 2 ms 988 KB Output is correct
5 Incorrect 15 ms 4440 KB Output isn't correct
6 Halted 0 ms 0 KB -