답안 #305923

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
305923 2020-09-24T05:24:59 Z Celloboy Job Scheduling (CEOI12_jobs) Java 11
0 / 100
1000 ms 65552 KB

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)