Submission #632628

#	Time	Username	Problem	Language	Result	Execution time	Memory
632628		Richem	Self Study (JOI22_ho_t2)	C++14	100 / 100	403 ms	11452 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++)
	    cours[i][0] = max(cours[i][0], cours[i][1]);
}
 
int calc(int petit, int grand) {
	int rep = grand / petit;
 
	if(rep * petit < grand)
		rep++;
	return rep;
}
 
int nbRestant[MAX_COURS];
bool possible(int k) {
	int nbDispo = nbCours * nbSemaine;
	
	for(int cur = 0; cur < nbCours; cur++) {
		if(k <= cours[cur][0] * nbSemaine) {
			nbDispo -= calc(cours[cur][0], k);
		}
		else {
			int restant = k - nbSemaine * cours[cur][0];
			nbDispo = nbDispo - nbSemaine - calc(cours[cur][1], restant);
            if(nbDispo < 0) return 0;
		}
	}
 
	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: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9