Submission #632594

#	Time	Username	Problem	Language	Result	Execution time	Memory
632594		Richem	Self Study (JOI22_ho_t2)	C++14	0 / 100	570 ms	7536 KiB

Main

#include <iostream>
#define int long long

using namespace std;

const int MAX_COURS = 3e5+42, INF = 1e18;

int nbCours, nbSemaine;

int cours[MAX_COURS][2];

void input() {
	cin >> nbCours >> nbSemaine;

	for(int k = 0; k < 2; k++) {
		for(int i = 0; i < nbCours; i++)
			cin >> cours[i][k];
	}

	for(int i = 0; i < nbCours; i++) {
		if(cours[i][1] > cours[i][0])
			swap(cours[i][0], cours[i][1]);
	}
}

int calc(int petit, int grand) {
	int rep = grand / petit;

	if(grand % petit != 0)
		rep++;
	return rep;
}

bool possible(int k) {
	int nbDispo = nbCours * nbSemaine;
	int nbRestant[MAX_COURS];

	for(int cur = 0; cur < nbCours; cur++) {
		int nbUtilise = min(nbSemaine, calc(cours[cur][0], k));
		nbDispo -= nbUtilise;
		nbRestant[cur] = k - nbUtilise * cours[cur][0];
	}

	for(int cur = 0; cur < nbCours; cur++) {
		if(nbRestant[cur] <= 0) continue;
		nbDispo -= calc(cours[cur][1], nbRestant[cur]);
	}

	return nbDispo >= 0;
}

int dicho(int deb, int fin) {
	while(deb < fin) {
		int milieu = (deb + fin+1) / 2;

		if(possible(milieu))
			deb = milieu;
		else
			fin = milieu-1;
	}

	return deb;
}

signed main() {
	input();
	cout << dicho(0, INF);
}

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