Submission #390552

#	Time	Username	Problem	Language	Result	Execution time	Memory
390552		AlexPop28	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	2 ms	716 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) {
    for (int j = 0; j < m; ++j) {
      pq.emplace(x[i][j], i); 
    }
  }
  vector<int> pos(n, m - 1);

  long long res = 0;
  for (int it = 0; it < n * m / 2; ++it) {
    int val, i; tie(val, i) = pq.top(); pq.pop();
    if (--pos[i] >= 0) pq.emplace(x[i][pos[i]], i);
    res += val;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= pos[i]; ++j) {
      res -= x[i][j];
    }
  }

  auto zeros = pos;
  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;
  }
  
  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;
}

• Subtask 1: 11 / 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