Submission #1254307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254307		vibhas	Self Study (JOI22_ho_t2)	Java	100 / 100	379 ms	72984 KiB

Main

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] course_study = new int[n];
        int[] self_study = new int[n];
        StringTokenizer st_course = new StringTokenizer(br.readLine());
        StringTokenizer st_self = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            course_study[i] = Integer.parseInt(st_course.nextToken());
            self_study[i] = Integer.parseInt(st_self.nextToken());
        }
        long b = 0;
        long e = 1000000000000000100L;
        while(b < e){
            long mid = ((b+e+1)/2);
            if(possible(mid, course_study, self_study, n, m)){
                b = mid;
            }else{
                e = mid-1;
            }
        }
        System.out.println(b);
    }
    public static boolean possible(long mid, int[] course_study, int[] self_study, int n, int m){
        long total_classes = (long) n*m;
        for(int i = 0; i < n; i++){
            int a = course_study[i];
            int s = self_study[i];
            long current = mid;
            long num_classes;
            if(a > s){
                num_classes = 0;
                if((long) a*m < current){
                    current -= (long)a*m;
                    num_classes += m;
                    num_classes += current/s;
                    if(current%s != 0){
                        num_classes++;
                    }
                }else{
                    num_classes = current/a;
                    if(current%a != 0) num_classes++;
                }
            }else{
                // s >= a
                num_classes = current / ((long) s);
                if(current%s != 0){
                    num_classes++;
                }
            }
            total_classes-=num_classes;
            if(total_classes < 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