import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 1번째 줄: N, M, K
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long K = Long.parseLong(st.nextToken());

        // 2번째 줄: X, Y
        st = new StringTokenizer(br.readLine());
        long X = Long.parseLong(st.nextToken()); // 1달러 지폐 수 (최대 10^15)
        long Y = Long.parseLong(st.nextToken()); // K달러 지폐 수 (최대 10^9)

        // 3번째 줄: A1 ... AN (디저트 가격)
        long[] A = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        // 4번째 줄: B1 ... BM (음료 가격) K달러만 받음
        long[] B = new long[M];
        st = new StringTokenizer(br.readLine());
        for (int j = 0; j < M; j++) {
            B[j] = Long.parseLong(st.nextToken());
        }

        long total_amount = X + K*Y;

        Arrays.sort(A);
        Arrays.sort(B);
        // remains 의 index는 음료 구매 수, value는 그 구매 후의 1달러 수
        long[] remains = new long[M+1];
        remains[0] = total_amount;
        for (int j = 1; j <= M; j++) {
            if(Y*K-B[j-1] >= 0) {
                // f1
                long paid_k = (B[j-1]+K-1)/K; 
                long rest = paid_k*K - B[j-1]; 
                Y -= paid_k;
                // f2 
                remains[j] = remains[j-1] -paid_k*K+ rest;
                // System.out.println(paid_k + " " + rest);
            } else {
                remains[j] = -1;
                break;
            }
        }


        // remains 의 각 금액에 따라 구매할 수 있는 디즈트의 최대개수를 구하기
        // M개수가 10^5수준, N을 그대로 순회하면 시간초과니 10^4 이하로 하기를 권장.
        // 이를 만족하는 방법은 logN의 이진탐색뿐.
        //remains 배열 따로 안만들고 위의 for문에서 바로 이진탐색 했으면 메모리절약 됐을 듯.
        long[] acc_A = new long[N+1];
        for (int i=1; i<=N; i++) {
            acc_A[i] = acc_A[i-1] + A[i-1];   
        
        }
        
        long max_v = 0;

        // f3 f4 
        for (int j=0; j<=M; j++) {
            // System.out.println(remains[j]);
            if(remains[j] == -1) break;

            
            long buy_count = j;
            int l = 0; // 뭐...디저트도 하나도 안살 수 있으니 l은 0으로 해야하나
            int r = N;
            int max_desert = 0;
            
            while (l<=r) {
                int m = (l+r)/2;
                // f5
                // m개 사기에는 돈이 부족하다 -> m을 줄여야지.
                if(acc_A[m] > remains[j]) r = m -1;
                else {
                    max_desert = m;
                    l = m+1;
                }
            }
            // System.out.println(max_v + " j" + j + " max_desert" +max_desert);

            max_v = Math.max(max_v, max_desert+j);
        }
        System.out.println(max_v);

        //feedback 
        //
        

        
    }
}

Embed on website

To embed this project on your website, copy the following code and paste it into your website's HTML: