Submission #1001028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001028		LucaLucaM	Team Contest (JOI22_team)	C++17	0 / 100	307 ms	46164 KiB

team

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <set>
#include <map>
#warning That's the baby, that's not my baby

typedef long long ll;

int dumb(int n, std::vector<int> a, std::vector<int> b, std::vector<int> c) {
  int answer = -1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (a[i] > a[j] && a[i] > a[k] && b[j] > b[i] && b[j] > b[k] && c[k] > c[i] && c[k] > c[j]) {
          answer = std::max(answer, a[i] + b[j] + c[k]);
        }
      }
    }
  }
  return answer;
}

int smart(int n, std::vector<int> a, std::vector<int> b, std::vector<int> c) {
  if (n < 3) {
    return -1;
  }
  int answer = 0;
  int maxA = *std::max_element(a.begin(), a.end());
  int maxB = *std::max_element(b.begin(), b.end());
  int maxC = *std::max_element(c.begin(), c.end());
  std::vector<int> A, B, C;
  for (int i = 0; i < n; i++) {
    int cnt = (a[i] == maxA) + (b[i] == maxB) + (c[i] == maxC);
    if (cnt <= 1) {
      A.push_back(a[i]);
      B.push_back(b[i]);
      C.push_back(c[i]);
    }
  }

  if ((int) A.size() == n) {
    return maxA + maxB + maxC;
  } else {
    return smart((int) A.size(), A, B, C);
  }
}

int full(int n, std::vector<int> a, std::vector<int> b, std::vector<int> c) {
  std::multiset<int> as, bs, cs;
  std::map<std::pair<int, int>, std::set<int>> AB, BC, AC;
  for (int i = 0; i < n; i++) {
    as.insert(a[i]);
    bs.insert(b[i]);
    cs.insert(c[i]);
    AB[{a[i], b[i]}].insert(i);
    BC[{b[i], c[i]}].insert(i);
    AC[{a[i], c[i]}].insert(i);
  }

  auto del = [&] (int i) {
    as.erase(as.find(a[i]));
    bs.erase(bs.find(b[i]));
    cs.erase(cs.find(c[i]));
    AB[{a[i], b[i]}].erase(i);
    BC[{b[i], c[i]}].erase(i);
    AC[{a[i], c[i]}].erase(i);
    if (AB[{a[i], b[i]}].empty()) {
      AB.erase({a[i], b[i]});
    }
    if (BC[{b[i], c[i]}].empty()) {
      BC.erase({b[i], c[i]});
    }
    if (AC[{a[i], c[i]}].empty()) {
      AC.erase({a[i], c[i]});
    }
  };

  while ((int) as.size() >= 3) {
    int maxA = *as.rbegin();
    int maxB = *bs.rbegin();
    int maxC = *cs.rbegin();
    auto it = AB.find({maxA, maxB});
    if (it != AB.end()) {
      int i = *(it -> second).begin();
      del(i);
      continue;
    }
    it = BC.find({maxB, maxC});
    if (it != BC.end()) {
      int i = *(it -> second).begin();
      del(i);
      continue;
    }
    it = AC.find({maxA, maxB});
    if (it != AC.end()) {
      int i = *(it -> second).begin();
      del(i);
      continue;
    }
    break;
  }
  if ((int) as.size() < 3) {
    return -1;
  } else {
    return *as.rbegin() + *bs.rbegin() + *cs.rbegin();
  }
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;
  std::vector<int> a(n), b(n), c(n);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i] >> b[i] >> c[i];
  }
  std::cout << full(n, a, b, c);

  return 0;
}

Compilation message (stderr)

team.cpp:8:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    8 | #warning That's the baby, that's not my baby
      |  ^~~~~~~
team.cpp: In function 'int smart(int, std::vector<int>, std::vector<int>, std::vector<int>)':
team.cpp:30:7: warning: unused variable 'answer' [-Wunused-variable]
   30 |   int answer = 0;
      |       ^~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27