제출 #1196368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196368		Gabp	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	401 ms	54412 KiB

tickets

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

long long int find_maximum(int k, vector<vector<int>> x) {
  int n = x.size(), m = x[0].size();
  long long int total = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      total += x[i][m - j - 1];
    }
  }
  
  vector<int> idx(n, 0);
  priority_queue<pair<int,int>> pq;
  for (int i = 0; i < n; i++) pq.push({-x[i][0] - x[i][m - k], i});
  int cnt = n * k / 2;
  while (cnt--) {
    auto [val, id] = pq.top(); pq.pop();
    total += val;
    idx[id]++;
    if (idx[id] < k) {
      pq.push({-x[id][idx[id]] - x[id][m - k + idx[id]], id});
    }
  }
  
  vector<int> lo = idx;
  vector<int> hi(n);
  for (int i = 0; i < n; i++) hi[i] = k - lo[i];
  
  vector<vector<int>> ans(n, vector<int>(m, -1));
  for (int i = 0; i < k; i++) {
    int l = n / 2, r = n / 2;
    for (int j = 0; j < n; j++) {
      if (lo[j] == 0) {
        ans[j][m - hi[j]] = i;
        hi[j]--;
        r--;
      } else if (hi[j] == 0) {
        lo[j]--;
        ans[j][lo[j]] = i;
        l--;
      }
    }
    for (int j = 0; j < n; j++) {
      if (lo[j] + hi[j] != k - i) continue;
      
      if (l) {
        lo[j]--;
        ans[j][lo[j]] = i;
        l--;
      } else {
        ans[j][m - hi[j]] = i;
        hi[j]--;
        r--;
      }
    }
  }
  
  allocate_tickets(ans);
  return total;
}

• 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