Submission #1145880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145880		andrewp	Self Study (JOI22_ho_t2)	C++20	64 / 100	120 ms	17588 KiB

Main

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(a) ((int)a.size())
const int N=3e5+5;
 
ll n, m;
ll a[N], b[N]; 
vector<pair<ll, pair<ll, ll>>> v;

bool check(ll mid) {   
   ll o=0;
   for (auto x:v) {
      ll mx=x.first, A=x.second.first, B=x.second.second; 
      if (A>=B) {
         ll tr=min((mid+mx-1)/mx, m);   
         if (tr*mx>=mid) {
            o+=(m-tr);  
         } 
         else {
            ll tr2=(mid-min((mid+mx-1)/mx, m)*mx+B-1)/B;  
            if (tr2>o) 
               return false;
            else 
               o-=tr2;  
         } 
      }
      else {
         ll tr=min((mid+mx-1)/mx, o);   
         if (tr*mx>=mid) {
            o+=m;
         }
         else { 
            ll tr2=(mid-min((mid+mx-1)/mx, o)*mx+mx-1)/mx;  
            if (tr2>m) 
               return false;
            else 
               o=m-tr2;  
         }
      }  
   } 
   return true; 
}

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

   cin >> n >> m;
   for (ll i=1; i<=n; i++) 
      cin >> a[i];
   for (ll i=1; i<=n; i++) 
      cin >> b[i];
   for (ll i=1; i<=n; i++) {
      v.pb(make_pair(max(a[i], b[i]), make_pair(a[i], b[i])));
   }
   sort(rall(v));
   ll lo=1, hi=(ll)(1e18), ans=0;
   while (lo<=hi) {
      ll mid=(lo+hi)/2;
      if (check(mid)) {
         lo=mid+1;
         ans=mid;
      }
      else {
         hi=mid-1; 
      }
   }  
   cout << ans << '\n'; 
}

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