제출 #390565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390565		AlexPop28	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	838 ms	76028 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<vector<int>> ans(n, vector<int>(m, -1));

  priority_queue<pair<int, int>> pq;
  for (int i = 0; i < n; ++i) {
    pq.emplace(x[i][m - 1] + x[i][k - 1], i); 
  }
  vector<int> pos(n, m - 1);
  vector<int> minus(n, k - 1);

  long long res = 0;
  for (int i = 0; i < n; ++i) for (int j = 0; j < k; ++j) res -= x[i][j];

  for (int it = 0; it < n * k / 2; ++it) {
    int val, i; tie(val, i) = pq.top(); pq.pop();
    --pos[i]; --minus[i];
    if (pos[i] >= m - k && minus[i] >= 0) pq.emplace(x[i][pos[i]] + x[i][minus[i]], i);
    res += val;
    // printf("val = %d, i = %d\n", val, i);
  }
  // cerr << res << endl;
  /*
  for (int i = 0; i < n; ++i) {
    // cerr << i << ": ";
    for (int j = 0; j <= k - (m - pos[i]); ++j) {
      res -= x[i][j];
      // cerr << j << ' ';
    }
    // cerr << endl;
  }
  */

  auto zeros = minus;
  vector<int> pos0(n), pos1(n);
  for (int i = 0; i < n; ++i) {
    pos[i] = max(pos[i], -1);
    pos0[i] = 0;
    pos1[i] = pos[i] + 1;
    zeros[i] += 1;
    // cerr << i << ' ' << zeros[i] << ' ' << pos1[i] << endl;
  }

  auto Comp = [&](int a, int b) {
    return zeros[a] > zeros[b];
  };
  
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  for (int it = 0; it < k; ++it) {
    sort(order.begin(), order.end(), [&](int a, int b) {
      return zeros[a] > zeros[b];
    });

    int bal = 0;
    for (int i : order) {
      if (bal < n / 2) {
        ans[i][pos0[i]++] = it;
        --zeros[i];
        ++bal;
      } else {
        ans[i][pos1[i]++] = it;
      }
    }
  }

  allocate_tickets(ans);
  return res;
}

컴파일 시 표준 에러 (stderr) 메시지

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:50:8: warning: variable 'Comp' set but not used [-Wunused-but-set-variable]
   50 |   auto Comp = [&](int a, int b) {
      |        ^~~~

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