제출 #529339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529339		nemethm	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	149 ms	10804 KiB

jobs

#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <queue>
#include <string>
#include <limits>
#include <map>
#include <algorithm>
#include <stack>

using namespace std;
using ll = long long int;
const ll mod = 1e9 + 7;

bool possible(vector<pair<int,int>>& v, int d, int m){
  priority_queue<pair<int,int>> q;
  int day = 1;
  for(auto i : v){
    q.push({-i.first, i.second});
    int sum = 0;
    while(!q.empty() && sum < m){
      auto p = q.top(); q.pop();
      p.first = -p.first;
      if(day > p.first + d){    //!!
        return false;
      }
      if(p.second > m - sum){
        q.push({-p.first, p.second - (m - sum)});
      }
      sum += p.second;
    }
    ++day;
  }
  return true;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, d, m;
  cin >> n >>d >> m;
  vector<pair<int,int>> v(m);
  for(int i = 0; i < m; ++i){
    cin >> v[i].first;
    v[i].second = i + 1;
  }
  sort(begin(v), end(v));
  vector<pair<int,int>> compressed;
  for(int i = 0; i < m; ++i){
    if(compressed.empty() || compressed.back().first != v[i].first){
      compressed.push_back(make_pair(v[i].first, 0));
    }
    ++compressed.back().second;
  }
  int l = 1, r = m;
  while(l < r){
    int middle = (l + r) / 2;
    if(possible(compressed, d, middle)){
      r = middle;
    }
    else{
      l = middle + 1;
    }
  }
  cout << l << endl;

} 

• Subtask 1: 0 / 100