Submission #718120

#	Time	Username	Problem	Language	Result	Execution time	Memory
718120		mychecksedad	Self Study (JOI22_ho_t2)	C++17	0 / 100	484 ms	13304 KiB

Main

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 3e5+100, M = 1e5+10, K = 20;


ll n, m, c, ls, rs, s;
array<ll, 2> a[N];
vector<array<ll, 2>> lt, rt;
void solve(){
  cin >> n >> m;
  for(int i = 0; i < n; ++i) cin >> a[i][0];
  for(int i = 0; i < n; ++i) cin >> a[i][1];

  for(int i = 0; i < n; ++i){
    if(a[i][0] >= a[i][1])
      lt.pb(a[i]);
    else
      rt.pb(a[i]);
  }

  sort(all(lt), [&](const array<ll, 2> &x, const array<ll, 2> &y){
    return x[0] > y[0];
  });

  sort(all(rt), [&](const array<ll, 2> &x, const array<ll, 2> &y){
    return x[1] > y[1];
  });

  ls = lt.size();
  rs = rt.size();

  ll l = 0, r = 1e18, ans = 0;

  while(l <= r){
    ll mid = (l+r) >> 1;
    bool ok = 1;

    s = 0;
    for(int i = 0; i < ls; ++i){
      c = (mid + lt[i][0] - 1) / lt[i][0]; 
      if(c > m){
        s -= (mid - lt[i][0] * m + (lt[i][1] - 1)) / lt[i][1];
      }else{
        s += m - c;
      }
    }
    if(rs == 0){
      if(s < 0){
        ok = 0;
      }else{
        ok = 1;
      }
    }else{
      for(int i = 0; i < rs; ++i){
        if(mid - m * rt[i][1] > 0){
          s -= (mid - m * rt[i][1] + (rt[i][1] - 1)) / rt[i][1];
        }else{
          s += m - (mid + rt[i][1] - 1) / rt[i][1];
        }
      }
    }


    if(ok && s >= 0){
      l = mid + 1;
      ans = mid;
      continue;
    }else{
      r = mid - 1;
      continue;
    }
  }

  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int T = 1, aa;
  // cin >> T;aa=T;
  while(T--){
    // cout << "Case #" << aa-T << ": ";
    solve();
    cout << '\n';
  }
  return 0;
 
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:87:14: warning: unused variable 'aa' [-Wunused-variable]
   87 |   int T = 1, aa;
      |              ^~

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