Submission #544811

#	Time	Username	Problem	Language	Result	Execution time	Memory
544811		blue	Self Study (JOI22_ho_t2)	C++17	100 / 100	345 ms	13832 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
using namespace std;

using pii = pair<int, int>;
using vpii = vector<pii>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
using vvi = vector<vi>;

#define sz(x) int(x.size())

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll N, M;
	cin >> N >> M;

	vll A(1+N), B(1+N);
	for(int i = 1; i <= N; i++) cin >> A[i];
	for(int i = 1; i <= N; i++)
	{
		cin >> B[i];
		A[i] = max(A[i], B[i]);
	}

	ll lo = 0, hi = 1'000'000'000'000'000'000LL;

	while(lo != hi)
	{
		ll target = (lo+hi)/2 + 1;

		vll remaining_goal(1+N);
		ll remaining_slots = 0;

		for(int i = 1; i <= N; i++)
		{
			ll classes = min(M, (target / A[i]) + bool(target % A[i]));

			remaining_goal[i] = max(0LL, target - classes * A[i]);
			remaining_slots += M - classes;
		}

		for(int i = 1; i <= N; i++)
		{
			ll curr = (remaining_goal[i] / B[i])  +  bool(remaining_goal[i] % B[i]);
			remaining_slots -= curr;
			if(remaining_slots < 0)
			{
				break;
			}
		}

		// cerr << target << " : " << remaining_slots << '\n';

		if(remaining_slots >= 0)
			lo = target;
		else
			hi = target - 1;
	}

	cout << lo << '\n';
}

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