Submission #8171409


Source Code Expand

Copy
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int N;
long long int K;

long long int A[200005], F[200005];

vector<long long int> VA, VF;

int IS_POSSIBLE(long long int W) {

	if (W < 0) { return -1; }

	long long int cnt = 0;

	for (int i = 0; i < N; i++) {
		cnt += max((long long int) 0, VA[i]- W / VF[i]);
	}

	//cout << "cnt= " << cnt <<  "K= " <<K << endl;

	if (cnt <= K) { return 1; }

	return -1;

}

long long int BINARY_SEARCH(void) {

	long long int left = -1;
	long long int right = 1000000000000000006;

	long long int med;

	while (right - left > 1) {
		med = (right + left) / 2;

		if (IS_POSSIBLE(med) == 1) { right = med; }
		else { left = med; }
	}

	return right;
}

int main(void) {

	cin >> N >> K;

	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		VA.push_back(A[i]);
	}

	for (int i = 1; i <= N; i++) {
		cin >> F[i];
		VF.push_back(F[i]);
	}


	sort(VA.begin(), VA.end());

	sort(VF.rbegin(), VF.rend());

	/*for (auto y : VA) { cout << " " << y; }
	cout << endl;

	for (auto y : VF) { cout << " " << y; }
	cout << endl;
	*/

	

	cout << BINARY_SEARCH()<< endl;
	
	return 0;
}

Submission Info

Submission Time
Task E - Gluttony
User LEE_0102
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1235 Byte
Status AC
Exec Time 284 ms
Memory 7408 KB

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 38
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_31.txt, sub1_32.txt, sub1_33.txt, sub1_34.txt, sub1_35.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sub1_01.txt AC 267 ms 7408 KB
sub1_02.txt AC 6 ms 384 KB
sub1_03.txt AC 96 ms 3444 KB
sub1_04.txt AC 23 ms 896 KB
sub1_05.txt AC 125 ms 3700 KB
sub1_06.txt AC 161 ms 4212 KB
sub1_07.txt AC 4 ms 384 KB
sub1_08.txt AC 221 ms 6896 KB
sub1_09.txt AC 80 ms 2168 KB
sub1_10.txt AC 134 ms 3828 KB
sub1_11.txt AC 174 ms 4340 KB
sub1_12.txt AC 74 ms 2040 KB
sub1_13.txt AC 35 ms 1148 KB
sub1_14.txt AC 120 ms 3700 KB
sub1_15.txt AC 98 ms 3444 KB
sub1_16.txt AC 154 ms 4084 KB
sub1_17.txt AC 125 ms 3700 KB
sub1_18.txt AC 255 ms 7408 KB
sub1_19.txt AC 256 ms 7408 KB
sub1_20.txt AC 256 ms 7408 KB
sub1_21.txt AC 255 ms 7408 KB
sub1_22.txt AC 256 ms 7408 KB
sub1_23.txt AC 257 ms 7408 KB
sub1_24.txt AC 253 ms 7408 KB
sub1_25.txt AC 256 ms 7408 KB
sub1_26.txt AC 276 ms 7408 KB
sub1_27.txt AC 275 ms 7408 KB
sub1_28.txt AC 276 ms 7408 KB
sub1_29.txt AC 275 ms 7408 KB
sub1_30.txt AC 274 ms 7408 KB
sub1_31.txt AC 275 ms 7408 KB
sub1_32.txt AC 276 ms 7408 KB
sub1_33.txt AC 284 ms 7408 KB
sub1_34.txt AC 4 ms 384 KB
sub1_35.txt AC 130 ms 3828 KB