Submission #954040

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954040	2024-03-27T06:44:54 Z	manishjha91	Self Study (JOI22_ho_t2)	C++17	0 / 100	432 ms	16024 KB

Main

#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);
		}
	}
	

	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)
		{
			if(m>=(mid+x-1)/x)
			{
				carry+= (m - (mid+x-1)/x);
			}
			else
			{
				ll need = (mid - x*m + y - 1)/y;
				
				carry -= need;
			}
		}
		
		
		return carry>=0;
	};
	
	
	ll l = 1;
	ll r = 1e18;
	
	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	348 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	452 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	3 ms	612 KB	Output is correct
11	Correct	178 ms	13428 KB	Output is correct
12	Correct	181 ms	14432 KB	Output is correct
13	Correct	136 ms	11544 KB	Output is correct
14	Incorrect	432 ms	16024 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	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	456 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	76 ms	7016 KB	Output is correct
10	Correct	50 ms	4656 KB	Output is correct
11	Correct	40 ms	3792 KB	Output is correct
12	Correct	30 ms	2780 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	596 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Incorrect	4 ms	600 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	348 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	452 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	3 ms	612 KB	Output is correct
11	Correct	178 ms	13428 KB	Output is correct
12	Correct	181 ms	14432 KB	Output is correct
13	Correct	136 ms	11544 KB	Output is correct
14	Incorrect	432 ms	16024 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	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	456 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	76 ms	7016 KB	Output is correct
10	Correct	50 ms	4656 KB	Output is correct
11	Correct	40 ms	3792 KB	Output is correct
12	Correct	30 ms	2780 KB	Output is correct
13	Correct	1 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	596 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Incorrect	4 ms	600 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	348 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	452 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	3 ms	612 KB	Output is correct
11	Correct	178 ms	13428 KB	Output is correct
12	Correct	181 ms	14432 KB	Output is correct
13	Correct	136 ms	11544 KB	Output is correct
14	Incorrect	432 ms	16024 KB	Output isn't correct
15	Halted	0 ms	0 KB	-