제출 #1242711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242711		kunzaZa183	카니발 티켓 (IOI20_tickets)	C++20	0 / 100	3093 ms	328 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

long long find_maximum(int k, vector<vector<int>> x) {
  int n = x.size();
  int m = x[0].size();
  vector<pair<int, int>> vpii;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      vpii.emplace_back(i, j);

  queue<int> qi;
  map<int, int> mii;
  for (int i = 0; i < k; i++) {
    mii[i] = n / 2;
    for (int j = 0; j < n / 2; j++)
      qi.push(i);
  }

  vector<vector<int>> answer(n, vector<int>(m, -1));

  sort(vpii.begin(), vpii.end(), [&](pair<int, int> a, pair<int, int> b) {
    return x[a.first][a.second] > x[b.first][b.second];
  });

  vector<set<int>> vsi(n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      vsi[i].insert(j);

  long long tot = 0;
  for (int i = 0; i < vpii.size(); i++) {
    auto [a, b] = vpii[i];

    auto it = mii.lower_bound(m - b - 1);
    if (it == mii.end()) {
      tot -= x[a][b];
    } else {
      tot += x[a][b];
      answer[a][b] = it->first;
      vsi[a].erase(it->first);
      it->second--;
      if (it->second == 0)
        mii.erase(it);
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (answer[i][j] == -1) {
        answer[i][j] = *vsi[i].begin();
        vsi[i].erase(vsi[i].begin());
      }
    }
  }

  allocate_tickets(answer);

  return tot;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10