oj.uz

Submission #954030

# Submission time Handle Problem Language Result Execution time Memory
954030 2024-03-27T06:27:00 Z manishjha91 Self Study (JOI22_ho_t2) C++17
0 / 100
 280 ms 15048 KB 
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using lld = long double;

// #ifndef ONLINE_JUDGE
// #include "E:\Personal\cpp_codes\debugalgo.h"
// #else
// #define debug(x)
// #endif


void solve(int tc)
{
	ll n,m;
	cin>>n>>m;
	
	vector<pair<ll,ll>> a(n);
	for(int i=0; i<n; i++)
	{
		cin>>a[i].first;
	}
	
	for(int i=0; i<n; i++) cin>>a[i].second;
	
	
	vector<pair<ll,ll>> largerA;
	vector<ll> largerB;
	
	for(int i=0; i<n; i++)
	{
		if(a[i].first>a[i].second)
		{
			largerA.push_back(a[i]);
		}
		else
		{
			largerB.push_back(a[i].second);
		}
	}
	
	sort(largerA.rbegin(),largerA.rend());
	sort(largerB.rbegin(),largerB.rend());
	
	// debug(largerA);
	// debug(largerB);
	
	auto feasible = [&](ll mid)
	{
		ll carry = 0;
		
		for(auto &x: largerB)
		{
			ll need = (mid + x-1)/x;
			
			carry += (m-need);
		}
		
		for(auto &[x,y]: largerA)
		{
			ll xval = x*m;
			
			if(xval>=mid)
			{
				carry+= (m - (mid+x-1)/x);
			}
			else
			{
				ll need = (mid - x*m + y - 1)/y;
				
				carry -= need;
			}
		}
		
		return carry>=0;
	};
	
	
	ll l = 0;
	ll r = 2e18;
	
	ll ans = 0;
	while(l<=r)
	{
		ll mid = l + (r-l)/2;
		
		if(feasible(mid))
		{
			ans = mid;
			l  = mid + 1;
		}
		else r = mid - 1;
	}
	
	cout<<ans<<"\n";
}

int main()
{
	ios_base:: sync_with_stdio(0);
	cin.tie(0);
// #ifndef ONLINE_JUDGE
// 	freopen("Error.txt", "w", stderr);
// #endif

	int tt = 1;
	// cin >> tt;
	for(int tc=1; tc<=tt; tc++)
	{
		solve(tc);
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 170 ms 10324 KB Output is correct
12 Correct 173 ms 11128 KB Output is correct
13 Correct 140 ms 10376 KB Output is correct
14 Incorrect 280 ms 15048 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 86 ms 4824 KB Output is correct
10 Correct 56 ms 3032 KB Output is correct
11 Correct 42 ms 2780 KB Output is correct
12 Correct 34 ms 2016 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Incorrect 5 ms 856 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 170 ms 10324 KB Output is correct
12 Correct 173 ms 11128 KB Output is correct
13 Correct 140 ms 10376 KB Output is correct
14 Incorrect 280 ms 15048 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 86 ms 4824 KB Output is correct
10 Correct 56 ms 3032 KB Output is correct
11 Correct 42 ms 2780 KB Output is correct
12 Correct 34 ms 2016 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Incorrect 5 ms 856 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 170 ms 10324 KB Output is correct
12 Correct 173 ms 11128 KB Output is correct
13 Correct 140 ms 10376 KB Output is correct
14 Incorrect 280 ms 15048 KB Output isn't correct
15 Halted 0 ms 0 KB -