Submission

Score: 100

User: njoop

Problemset: ห้องสมุดเมือง 3M

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-09 23:39:23

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

int a[105]= {0}, b[105] ={0};
int N;
int C(int X, int D) {
    return X-D+1;
}

pii B(int X) {
    int BC = 0;
    int R = 0;
    for (int i=0; i<N; i++) {
        int CV = C(X, a[i]);
        if (0 < CV && CV <= b[i]-a[i]) BC++;
        if (CV > b[i]-a[i]) {
            R += b[i]-a[i];
        } else if (0 < CV && CV <= b[i]-a[i]) {
            R += CV;
        }
    }
    return make_pair(R-BC+1, R);
}
int main() {
    cin >> N;
    int P = 0;
    for (int i=0; i<N; i++) {
        cin >> a[i] >> b[i];
        P += b[i]-a[i];
    }
    if(P == 1) {
        cout << a[0];
        return 0;
    }
    P /= 2;
    int L = 0;
    int R = 40000000;
    int M;
    //cout << P << "\n";
    while (L <= R) {
        M = L + (R-L)/2;
        //cout << M << " ";
        auto [RX, RY] = B(M);
        //cout << RX << " " << RY << "\n";
        if (RX>RY) {
            if (P<=RY) {
                R = M-1;
            } else {
                L = M+1;
            }
        } else if (RX<=P && P <=RY && RX<=RY) {
            cout << M;
            return 0;
        } else if (RY < P) {
            L = M+1;
        } else if (P < RX) {
            R = M-1;
        }
    }
    return 0;
}