oj.uz

Submission #1001028

# Submission time Handle Problem Language Result Execution time Memory
1001028 2024-06-18T13:05:22 Z LucaLucaM Team Contest (JOI22_team) C++17
0 / 100
 307 ms 46164 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 307 ms 46164 KB Output is correct
12 Incorrect 192 ms 30800 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 307 ms 46164 KB Output is correct
12 Incorrect 192 ms 30800 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 307 ms 46164 KB Output is correct
12 Incorrect 192 ms 30800 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 307 ms 46164 KB Output is correct
12 Incorrect 192 ms 30800 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -