Submission #1149860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149860		henriess	Self Study (JOI22_ho_t2)	C++20	54 / 100	143 ms	4936 KiB

Main

#include <bits/stdc++.h>
using namespace std;

static const long long INF = 1000000000000000000LL; // 1e18

long long N, M;
vector<long long> A, B;

bool check_feasible(long long X) {
    // We'll keep track of how many "attends" and "skips"
    // are required in total to give *every* course i
    // at least X comprehension.
    long long totalAttend = 0;
    long long totalSkip   = 0;

    // We know N*M fits in 64-bit up to ~3e14. So no overflow here.
    long long maxSlots = (long long)N * M;

    for(int i = 0; i < N; i++){
        // 1) Calculate how many attends (course i's own classes) are needed:
        //    attend_i = min(M, ceil(X / A_i))
        //    because we cannot attend i more than M times
        long long needAttend;
        if (A[i] == 0) {
            // theoretically impossible if A[i] can be 1..1e9, 
            // but just in case
            needAttend = 0; 
        } else {
            needAttend = (X + A[i] - 1) / A[i]; // ceil
            if (needAttend > M) needAttend = M;
        }

        // 2) Comprehension from those attends:
        long long gained = needAttend * A[i];

        // 3) The leftover that must be covered by self-study:
        long long leftover = X - gained;
        if (leftover < 0) leftover = 0;

        // 4) How many self-studies to cover leftover?
        //    skip_i = ceil(leftover / B[i]) if B[i] != 0
        long long needSkip;
        if (B[i] == 0) {
            // again, problem constraints say B[i]>=1, but just be safe
            needSkip = (leftover > 0 ? INF : 0);
        } else {
            needSkip = (leftover + B[i] - 1) / B[i];
        }

        totalAttend += needAttend;
        totalSkip   += needSkip;

        // As soon as totalAttend+totalSkip > N*M, we can stop
        // because we know it's not feasible
        if (totalAttend + totalSkip > maxSlots) {
            return false;
        }
    }

    // If we fit in the schedule, it's feasible
    return (totalAttend + totalSkip <= maxSlots);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    A.resize(N);
    B.resize(N);

    long long maxAB = 0; // track max(A[i], B[i]) for an upper bound
    for(int i=0; i<N; i++){
        cin >> A[i];
        maxAB = max(maxAB, A[i]);
    }
    for(int i=0; i<N; i++){
        cin >> B[i];
        maxAB = max(maxAB, B[i]);
    }

    // We'll binary-search on [0, maxPossible], 
    // a safe upper bound is maxAB * M,
    // because in the absolute best case we could attend 
    // M times in a course with the largest A or skip M times with largest B.
    // But to be safe we can also just use 1e18 (INF) as an upper bound.
    long long left = 0;
    long long right = maxAB * M; // or min(maxAB * M, 1e18)
    if (right < 0) right = 1000000000000000000LL; // fallback to 1e18 if overflow

    long long answer = 0;

    while (left <= right) {
        long long mid = (left + right) / 2;
        if (check_feasible(mid)) {
            answer = mid;     // mid is feasible, try for a bigger one
            left = mid + 1;
        } else {
            right = mid - 1;  // mid not feasible
        }
    }

    cout << answer << "\n";
    return 0;
}

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