Submission #1242766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242766		kunzaZa183	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	319 ms	61760 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();

  priority_queue<pair<int, int>> pqai3;

  vector<vector<int>> vvi(n, vector<int>(m, 1));
  vector<int> l(n), r(n);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++)
      vvi[i][j] = 0;

    l[i] = k - 1, r[i] = m - 1;
  }

  for (int i = 0; i < n; i++)
    pqai3.emplace(x[i][l[i]] + x[i][r[i]], i);
  for (int i = 0; i < n / 2 * k; i++) {
    auto [add, in] = pqai3.top();
    // cout << add << " " << in << "\n";
    pqai3.pop();

    assert(vvi[in][l[in]] == 0);
    vvi[in][l[in]] = 1;
    assert(vvi[in][r[in]] == 1);
    vvi[in][r[in]] = 2;

    r[in]--, l[in]--;

    if (l[in] > 0) {
      pqai3.emplace(x[in][l[in]] + x[in][r[in]], in);
    }
  }

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

  vector<int> all(n);
  iota(all.begin(), all.end(), 0);
  vector<int> twos(n);
  for (int i = 0; i < n; i++) {
    l[i] = 0, r[i] = m - 1;
    for (int j = 0; j < m; j++) {
      if (vvi[i][j] == 2)
        twos[i]++;
    }
  }

  for (int i = 0; i < k; i++) {
    sort(all.begin(), all.end(),
         [&](int a, int b) { return twos[a] < twos[b]; });

    for (int j = 0; j < n / 2; j++) {
      ans[all[j]][l[all[j]]++] = i;
    }
    for (int j = n / 2; j < n; j++) {
      twos[all[j]]--;
      ans[all[j]][r[all[j]]--] = i;
    }
  }

  allocate_tickets(ans);

  long long tot = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      // cout << i << ' ' << j << " " << vvi[i][j] << " " << x[i][j] << "\n";
      if (vvi[i][j] == 0)
        tot -= x[i][j];
      else if (vvi[i][j] == 2)
        tot += x[i][j];
    }
  }

  return tot;
}

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