Submission #78558

#	Time	Username	Problem	Language	Result	Execution time	Memory
78558		MrTEK	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	262 ms	8236 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;

vector <int> v[N];

int n,d,m;

bool check(int mach) {
  queue <int> Q;
  for (int i = 1 ; i <= n ; i++) {
    int temp = mach;
    while(Q.empty() == false && temp) {
      Q.pop();
      temp--;
    }
    for (int j = 1; j <= max(0,(int)v[i].size() - temp) ; j++)
      Q.push(i);
    if (Q.empty() == false && i+ 1 - Q.front() > d)
      return false;
  }
  // cerr << mach << " " << (int) Q.size() << endl;
  return Q.empty() == true;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> d >> m;
  for (int i = 1 ; i <= m ; i++) {
    int a;
    cin >> a;
    v[a].push_back(i);
  }
  int l = 1,r = m;
  while(l < r) {
    int mid = (l + r - 1) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  cout << l << endl;
  for (int i = 1 ; i <= n ; i++) {
    cout << "0" << endl;
  }
}

• Subtask 1: 100 / 100