QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200576#6632. Minimize Medianhacker_johnRE 0ms0kbC++142.0kb2023-10-04 17:38:282023-10-04 17:38:29

Judging History

你现在查看的是最新测评结果

  • [2023-10-04 17:38:29]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-04 17:38:28]
  • 提交

answer

#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define int long long
#define pb push_back
#define LL long long
#define endl "\n"

const int N = 1e6 + 10;
const int INF = 1e10;

using namespace std;

int a[N], b[N], n, m, k;

inline bool check(int haha) {
	
	int sum = 0;
	
	for (register int i = 1; i <= (n + 1) / 2; i ++ ) {
		
		if(a[i] <= haha) continue;
		
		int tmp1 = ceil(1.0 * a[i] / haha), tmp2 = a[i] / haha; 
		
		int tmp;
		
		if(haha >= a[i] / tmp2) tmp = tmp2;
		
		else tmp = tmp1;
		
		sum += b[tmp];
		
	}
	
	if(sum <= k) return true;
	
	return false;
	
}

inline bool t_check() {
	
	int sum = 0;
	
	for (register int i = 1; i <= (n + 1) / 2; i ++ ) {
		
		sum += b[a[i] + 1];
		
	}
	
	if(sum <= k) return true;
	
	return false;
	
}

void solve(){
	
	std::cin >> n >> m >> k;
	
	for (register int i = 1; i <= n; i ++ ) {
		
		std::cin >> a[i];
		
	}
	
	std::sort(a + 1, a + n + 1);
	
	for (register int i = 1; i <= m; i ++ ) {
		
		std::cin >> b[i];
		
	}
	
	for (register int i = m; i >= 1; i -- ) b[i] = std::min(b[i], b[i + 1]);
	
	for (register int i = 2; i <= m; i ++ ) {
		
		int mm = m / b[i];
		
		mm = std::min(mm, i);
		
		for (register int j = 2; j <= mm; j ++ ) {
			
			b[i * j] = std::min(b[i * j], b[j] + b[i]);
			
		}
		
	}
	
	b[m + 1] = INF;
	
	for (register int i = 2; i <= m; i ++ ) b[m + 1] = std::min(b[m + 1], b[i] + b[(int)ceil(1.0 * (m + 1) / i)]);
	
	for (register int i = m - 1; i >= 1; i -- ) {
		
		b[i] = std::min(b[i], b[i + 1]);
		
	}
	
	int l = 1, r = INF;
	
	while(l < r) {
		
		int mid = (l + r) / 2;
		
		if(check(mid)) r = mid;
		
		else l = mid + 1;
		
	}
	
	if(t_check()) l = 0;
	
	std::cout << l << '\n';
	
}
signed main() {
	
	std::ios::sync_with_stdio(false);
	
	std::cin.tie(0);
	
	int T;
	
	T = 1;
	
	std::cin >> T;
	
	while(T --) {
		
		solve();
		
	}
	
	return 0;
	
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

3
3 5 0
2 5 2
3 2 4 6 13
3 5 3
2 5 3
3 2 4 6 13
3 5 6
2 5 2
3 2 4 6 13

output:


result: