Submission #632610

#	Time	Username	Problem	Language	Result	Execution time	Memory
632610		Richem	Self Study (JOI22_ho_t2)	C++14	0 / 100	568 ms	11132 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];
	}
}
 
int calc(int petit, int grand) {
	int rep = grand / petit;
 
	if(grand % petit != 0)
		rep++;
	return rep;
}

int nbRestant[MAX_COURS];
bool possible(int k) {
	int nbDispo = nbCours * nbSemaine;
 
	for(int cur = 0; cur < nbCours; cur++) {
		int truc = max(cours[cur][0], cours[cur][1]);
		int nbUtilise = min(nbSemaine, calc(truc, k));
		nbDispo -= nbUtilise;
		nbRestant[cur] = k - nbUtilise * truc;
	}
	
 
	for(int cur = 0; cur < nbCours; cur++) {
		if(nbRestant[cur] <= 0) continue;
		nbDispo -= calc(cours[cur][1], nbRestant[cur]);
	}
 
	return nbDispo >= 0ll;
}
 
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