답안 #632588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
632588	2022-08-20T11:34:14 Z	Richem	Self Study (JOI22_ho_t2)	C++14	0 / 100	586 ms	13184 KB

Main

#include <iostream>
#define int long long

using namespace std;

const int MAX_COURS = 3e5, 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.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	3 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	3 ms	2608 KB	Output is correct
5	Correct	2 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2644 KB	Output is correct
9	Correct	2 ms	2644 KB	Output is correct
10	Correct	8 ms	2772 KB	Output is correct
11	Correct	392 ms	13184 KB	Output is correct
12	Correct	403 ms	13020 KB	Output is correct
13	Incorrect	586 ms	11104 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	2 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2612 KB	Output is correct
9	Correct	213 ms	7916 KB	Output is correct
10	Correct	135 ms	6008 KB	Output is correct
11	Correct	99 ms	5172 KB	Output is correct
12	Correct	93 ms	4664 KB	Output is correct
13	Correct	3 ms	2644 KB	Output is correct
14	Correct	2 ms	2644 KB	Output is correct
15	Correct	2 ms	2612 KB	Output is correct
16	Correct	2 ms	2644 KB	Output is correct
17	Correct	2 ms	2644 KB	Output is correct
18	Incorrect	11 ms	2736 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	3 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	3 ms	2608 KB	Output is correct
5	Correct	2 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2644 KB	Output is correct
9	Correct	2 ms	2644 KB	Output is correct
10	Correct	8 ms	2772 KB	Output is correct
11	Correct	392 ms	13184 KB	Output is correct
12	Correct	403 ms	13020 KB	Output is correct
13	Incorrect	586 ms	11104 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	2 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2612 KB	Output is correct
9	Correct	213 ms	7916 KB	Output is correct
10	Correct	135 ms	6008 KB	Output is correct
11	Correct	99 ms	5172 KB	Output is correct
12	Correct	93 ms	4664 KB	Output is correct
13	Correct	3 ms	2644 KB	Output is correct
14	Correct	2 ms	2644 KB	Output is correct
15	Correct	2 ms	2612 KB	Output is correct
16	Correct	2 ms	2644 KB	Output is correct
17	Correct	2 ms	2644 KB	Output is correct
18	Incorrect	11 ms	2736 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	3 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	3 ms	2608 KB	Output is correct
5	Correct	2 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2644 KB	Output is correct
9	Correct	2 ms	2644 KB	Output is correct
10	Correct	8 ms	2772 KB	Output is correct
11	Correct	392 ms	13184 KB	Output is correct
12	Correct	403 ms	13020 KB	Output is correct
13	Incorrect	586 ms	11104 KB	Output isn't correct
14	Halted	0 ms	0 KB	-