oj.uz

Submission #78557

# Submission time Handle Problem Language Result Execution time Memory
78557 2018-10-06T09:51:49 Z MrTEK Job Scheduling (CEOI12_jobs) C++14
0 / 100
 141 ms 8144 KB 
#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;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3444 KB Unexpected end of file - int32 expected
2 Incorrect 15 ms 3532 KB Unexpected end of file - int32 expected
3 Incorrect 15 ms 3532 KB Unexpected end of file - int32 expected
4 Incorrect 16 ms 3728 KB Unexpected end of file - int32 expected
5 Incorrect 17 ms 3728 KB Unexpected end of file - int32 expected
6 Incorrect 17 ms 3728 KB Unexpected end of file - int32 expected
7 Incorrect 15 ms 3728 KB Unexpected end of file - int32 expected
8 Incorrect 18 ms 3728 KB Unexpected end of file - int32 expected
9 Incorrect 16 ms 3728 KB Unexpected end of file - int32 expected
10 Incorrect 21 ms 3728 KB Unexpected end of file - int32 expected
11 Incorrect 15 ms 3728 KB Unexpected end of file - int32 expected
12 Incorrect 29 ms 3880 KB Unexpected end of file - int32 expected
13 Incorrect 40 ms 5076 KB Unexpected end of file - int32 expected
14 Incorrect 74 ms 5800 KB Unexpected end of file - int32 expected
15 Incorrect 56 ms 5800 KB Unexpected end of file - int32 expected
16 Incorrect 107 ms 6836 KB Unexpected end of file - int32 expected
17 Incorrect 129 ms 8108 KB Unexpected end of file - int32 expected
18 Incorrect 97 ms 8108 KB Unexpected end of file - int32 expected
19 Incorrect 121 ms 8108 KB Unexpected end of file - int32 expected
20 Incorrect 141 ms 8144 KB Unexpected end of file - int32 expected