Submission #1136660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136660		LinkedArray	Sails (IOI07_sails)	C++20	0 / 100	1095 ms	5704 KiB

sails

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

using ll = long long;
#define pb push_back

const int NUM_ROWS = 1e5;

struct Row {
  int num_sails;
  int row_id;
};

struct RowCustomComparator {
  bool operator()(Row a, Row b) const {
    if (a.num_sails == b.num_sails) {
      return a.row_id < b.row_id;
    }
    return a.num_sails < b.num_sails;
  }
};

vector<int> h, k;
set<Row, RowCustomComparator> rows;

int get_inef () {
  int ans = 0;
  for (auto e : rows) {
    cout << "{" << e.row_id << ", " << e.num_sails << "}\n";
    ans += e.num_sails;
  }
  return ans;
}

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, i, j, max_height, ans;
  Row row, min_row;

  cin >> n;

  h = vector<int>(n + 1);
  k = vector<int>(n + 1);
  max_height = 0;
  for (i = 1; i <= n; i++) {
    cin >> h[i] >> k[i];
    max_height = max(max_height, h[i]);
  }

  for (i = 1; i <= max_height; i++) {
    row = {0, i};
    rows.insert(row);
  }

  ans = 0;
  for (i = n; i >= 1; i--) {
    // cout << get_inef() << "\n";
    vector<bool> was_visited(h[i] + 1, false);
    for (j = 1; j <= k[i]; j++) {
      auto it = rows.begin();
      while ((*it).row_id > h[i] || was_visited[(*it).row_id]) {
        it++;
      }
      min_row = *it;
      was_visited[min_row.row_id] = true;
      ans += min_row.num_sails;
      rows.erase(min_row);
      min_row.num_sails++;
      rows.insert(min_row);
    }
    // cout << "!! " << ans << " !!\n";
  }
  cout << ans << "\n";
  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10