Submission #588452

#	Time	Username	Problem	Language	Result	Execution time	Memory
588452		lorenzoferrari	Teams (IOI15_teams)	C++17	34 / 100	4088 ms	25432 KiB

teams

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

int n;
vector<int> a, b;
vector<array<int, 2>> v;

int can(int M, int K[]) {
  sort(K, K + M);
  map<int, int> frq;
  for (int j = 0, i = 0; j < M; ++j) {
    for (; i < n && v[i][0] <= K[j]; ++i) ++frq[v[i][1]];
    auto it = frq.lower_bound(K[j]);
    while (K[j] && it != frq.end()) {
      if (it->second <= K[j]) {
        K[j] -= it->second;
        it->second = 0;
      } else {
        it->second -= K[j];
        K[j] = 0;
      }
      ++it;
    }
    // cerr << K[j] << endl;
    if (K[j]) return 0;
  }
  return 1;
}

void init(int N, int A[], int B[]) {
  n = N;
  a.resize(n);
  b.resize(n);
  v.resize(n);
  for (int i = 0; i < n; ++i) {
    a[i] = A[i];
    b[i] = B[i];
    v[i] = {a[i], b[i]};
  }
  sort(v.begin(), v.end());
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23