Submission #1293269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293269		Minbaev	Self Study (JOI22_ho_t2)	C++20	10 / 100	47 ms	9820 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define int     long long
#define ar      array

#define rnd(a, b)   uniform_int_distribution<int>(a, b)(rng)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

namespace FAST {
    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const int inf = 3e18 + 7;
const int mod = 1e9 + 7;
const int N = 6e5 + 5;
const int md = 998244353;

int n,m,k;
vector<int>a(N), b(N);

int solve(){
	
	//~ cin >> n >> m;
	//~ vector<int>a(n), b(n);
	//~ cin >> a >> b;
	
	int l = 1, r = 3e18, ans = -1;
	while(l <= r){
		int mid = (l + r) / 2;
		//~ mid = 18;
		int cnt = 0;
		for(int i = 0;i<n;i++){
			int mx = max(a[i], b[i]);
			if(mx * m >= mid){
				int cont = (mid + mx - 1) / mx;
				cnt += m - cont;
			}
		}
		
		for(int i = 0;i<n;i++){
			int mx = max(a[i], b[i]);
			if(mx * m >= mid)continue;
			int u = mid;
			u -= m * mx;
			int cont = (u + b[i] - 1) / b[i];
			cnt -= cont;
		}
		
		if(cnt >= 0){
			l = mid + 1;
			ans = mid;
		}
		else r = mid - 1;
		//~ return;
	}
	
	return ans;
}

int check(){
	int mn = inf;
	for(int i = 0;i<n;i++){
		umin(mn, max(a[i], b[i]));
	}
	return mn;
}

/*


*/
 signed main()
{
//  freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    //~ int tt=1;//cin >> tt;
    //~ while(tt--)solve();	
    
    cin >> n >> m;
    for(int i = 0;i<n;i++)cin >> a[i];
    for(int i = 0;i<n;i++)cin >> b[i];
    
    cout << check() << "\n";
    
    //~ int cnt = 1;
    //~ while(true){
		//~ for(int i = 0;i<n;i++){
			//~ a[i] = rnd(1, 1000000000);
			//~ b[i] = rnd(1, 1000000000);
		//~ }
		
		//~ if(solve() != check()){
			//~ for(int i = 0;i<n;i++)cout << a[i] << " ";
			//~ cout << "\n";
			//~ for(int i = 0;i<n;i++)cout << b[i] << " ";
			//~ cout << "\n";
			//~ exit(0);
		//~ }
		
		//~ cout << "Tests passed" << " " << cnt++ << endl;
	//~ }

}

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