import java.io.*;
import java.util.*;
public class jobs {
static int N, D, M;
static ArrayList<Group> arr;
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new ArrayList<Group>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
arr.add(new Group(Integer.parseInt(st.nextToken()), i+1));
//System.out.println(arr[i]);
}
Collections.sort(arr);
int a = 0, b = M;
while(a!=b) {
int mid = (a+b)/2;
if(works(mid)) {
b=mid;
}else {
a=mid+1;
}
//System.out.println(a+" "+ b);
}
pw.println(a);
/*
int point1 = 0;
for(int i = 0; i < N; i++) {
int curr = point1 + a;
while(point1 < M && point1 < curr) {
pw.print(arr.get(point1).b + " ");
point1++;
}
pw.println("0");
}
*/
//System.out.println(a);
//pw.println(a);
}
private static boolean works(int mid) {
// TODO Auto-generated method stub
int prevDay[] = new int[mid];
for(int i = 0; i < M;) {
for(int j = i; j < i +mid; j++) {
if(j >= M) {
break;
}
if(arr.get(j).a> prevDay[j-i]) {
prevDay[j-i] = arr.get(j).a;
}else {
int temp = prevDay[j-i]-arr.get(j).a+1;
if(temp > D) {
return false;
}
prevDay[j-i] = temp+prevDay[j-i];
}
}
i+=mid;
if(i >= M) {
break;
}
}
return true;
}
public static class Group implements Comparable<Group> {
int a,b;
// Constructor
public Group(int a, int b) {
this.a = a;
this.b = b;
}
public String toString()
{
return this.a + " " + this.b;
}
@Override
public int compareTo(Group other) {
return (int) (a-other.a);
}
@Override
public boolean equals(Object other) {
Group that = (Group) other;
return that.b ==b;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
344 ms |
26864 KB |
Unexpected end of file - int32 expected |
2 |
Incorrect |
321 ms |
26784 KB |
Unexpected end of file - int32 expected |
3 |
Incorrect |
362 ms |
27444 KB |
Unexpected end of file - int32 expected |
4 |
Incorrect |
309 ms |
26792 KB |
Unexpected end of file - int32 expected |
5 |
Incorrect |
340 ms |
26880 KB |
Unexpected end of file - int32 expected |
6 |
Incorrect |
308 ms |
26528 KB |
Unexpected end of file - int32 expected |
7 |
Incorrect |
345 ms |
28136 KB |
Unexpected end of file - int32 expected |
8 |
Incorrect |
315 ms |
26848 KB |
Unexpected end of file - int32 expected |
9 |
Incorrect |
501 ms |
26284 KB |
Unexpected end of file - int32 expected |
10 |
Incorrect |
508 ms |
26212 KB |
Unexpected end of file - int32 expected |
11 |
Incorrect |
538 ms |
27408 KB |
Unexpected end of file - int32 expected |
12 |
Runtime error |
764 ms |
40040 KB |
Memory limit exceeded |
13 |
Execution timed out |
1056 ms |
59496 KB |
Time limit exceeded |
14 |
Execution timed out |
1051 ms |
59388 KB |
Time limit exceeded |
15 |
Execution timed out |
1118 ms |
59892 KB |
Time limit exceeded |
16 |
Runtime error |
513 ms |
65548 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
17 |
Runtime error |
446 ms |
65552 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
18 |
Runtime error |
508 ms |
65548 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
19 |
Runtime error |
434 ms |
65548 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
20 |
Runtime error |
544 ms |
65544 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |