Submission #703372

#	Time	Username	Problem	Language	Result	Execution time	Memory
703372		niter	Self Study (JOI22_ho_t2)	C++14	0 / 100	564 ms	5588 KiB

Main

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define pii pair<long long,int>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define STL(i, x) for(auto &i:x) cout << i << " "; cout << "\n";
using namespace std;

long long a[300050], b[300050], as[300050];

/*ostream& operator<<(ostream &os, pii XXX){
    cout << "[" << XXX.ff << ", " << XXX.ss << "]";
}
void db(){
    cout << "\n";
}
template<class T, class ...U>
void db(T XXX, U ...YYY){
    cout << XXX;  db(YYY...);
}*/

int main(){
    long long n, m, all;
    cin >> n >> m;
    all = n * m;
    loop(i,0,n) cin >> a[i];
    loop(i,0,n) cin >> b[i];
    long long l = 1, r = (long long)(1e18), mid;
    long long cost, tmp_pay, classes;
    while(l != r){
        mid = (l + r + 1) >> 1;
        classes = 0;
        loop(i,0,n){
            cost = mid;
            if(b[i] >= a[i]){
                classes += ((cost-1) / b[i] + 1);
            }
            else{
                tmp_pay = min(((cost-1) / a[i] + 1), m);
                classes += tmp_pay;
                cost -= tmp_pay * a[i];
                if(cost <= 0) continue;

                tmp_pay = ((cost-1) / b[i] + 1);
                classes += tmp_pay;
            }
            //db(i, ' ', classes);
        }
        if(classes > all){
            r = mid - 1;
        }
        else{
            l = mid;
        }
    }
    cout << l << "\n";
    return 0;
}
/*
3 3
19 4 5
2 6 2
*/

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