Submission #1145914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145914		andrewp	Self Study (JOI22_ho_t2)	C++20	100 / 100	307 ms	11796 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]; 

bool check(ll mid) {   
   vector<ll> c;
   c.pb(0);
   for (int i=1; i<=n; i++) {
      c.pb((max(a[i], b[i])*m));
   }
   ll tot=0;
   for (int i=1; i<=n; i++) {
      if (tot>=(ll)(1e18)) 
         break;
      ll v=c[i];
      if (mid==v) 
         continue;
      else if (mid>v) {
         ll kol=((mid-v)/b[i]);
         if (((mid-v)%b[i])!=0) 
            ++kol;
         tot+=kol;
      }
      else {
         tot-=((v-mid)/max(a[i], b[i]));
      }
   }  
   return (tot<=0);
}  

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]; 
   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: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9