Submission #1263055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263055		vampirr	Self Study (JOI22_ho_t2)	Java	100 / 100	853 ms	166436 KiB

Main

import java.util.*;
public class Main {
	static int N,M;
	static int[] classes,self;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		M = in.nextInt();
		classes = new int[N];
		self = new int[N];
		for (int i=0; i<N; i++) {
			classes[i]=in.nextInt();
		}
		for (int i=0; i<N; i++) {
			self[i]=in.nextInt();
		}
		in.close();
		
		long lo=0; long hi=(long)1e18; long res=-1;
		while (lo<=hi) {
			long mid=(lo+hi)/2;
			if (works(mid)) {
				res=mid;
				lo=mid+1;
			}else {
				hi=mid-1;
			}
		}
		System.out.println(res);

	}
	
	public static boolean works(long goal) {
		long hours = ((long)N)*((long)M);
		
		for (int i=0; i<N; i++) {
			long required=goal;
			if (classes[i]>self[i]) {
				long needed = required/classes[i];
				if (required % classes[i] != 0) {
					needed++;
				}
				needed = Math.min(needed, M);
				
				required = Math.max(0L, required - needed*classes[i]);
				hours-=needed;
			}
			
			long needed = required/self[i];
			if (required % self[i] != 0) {
				needed++;
			}

			hours-=needed;
			if (hours<0) {
				return false;
			}
			
		}
		return true;
	}

}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9