QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226377#6632. Minimize MedianxuxubaobaoWA 82ms5588kbC++171.3kb2023-10-25 21:41:472023-10-25 21:41:47

Judging History

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

  • [2023-10-25 21:41:47]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:5588kb
  • [2023-10-25 21:41:47]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using PII = pair<int,int>;
using ll = long long;

constexpr int N = 2e6 + 10;

ll w[N];
ll c[N];
int n, m, k;

bool check(ll u) {
	ll cur = 0;
	if(u == 0) {
		for(int i = 1; i <= n / 2 + 1; i ++) {
			cur += c[w[i] + 1];
		}
	}
	else {
		for(int i = 1; i <= n / 2 + 1; i ++) {
			cur += c[(w[i] + u - 1) / u];
		}
	}
	return cur <= k;
}

void solve() {
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i ++) {
		cin >> w[i];
	}
	for(int i = 1; i <= m + 10; i ++) c[i] = 1 << 29;
	for(int i = 1; i <= m; i ++) {
		cin >> c[i];
	}
	for(int i = 1; i <= m; i ++) {
		for(int j = 1; i * j <= m; j ++) {
			c[i * j] = min(c[i * j], c[i] + c[j]);
		}
	}
	for(int i = m; i >= 1; i --) {
		c[i] = min(c[i], c[i + 1]);
	}
	int j = 1;
	for(int i = m; i >= 2; i --) {
		while(j < m && i * j <= m) j ++;
		c[m + 1] = min(c[m + 1], c[i] + c[j]);
	}
	c[1] = 0;
	for(int i = m; i >= 1; i --) {
		c[i] = min(c[i], c[i + 1]);
	}
	sort(w + 1, w + 1 + n);
	ll l = 0, r = 1ll << 29;
	while(r > l) {
		ll mid = (l + r) >> 1;
		if(check(mid)) {
			r = mid;
		}
		else l = mid + 1;
	}
	cout << l << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	cin >> t;
	while(t --){
		solve();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5588kb

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:

2
2
1

result:

ok 3 number(s): "2 2 1"

Test #2:

score: -100
Wrong Answer
time: 82ms
memory: 5472kb

input:

100000
5 10 5
3 7 1 10 10
11 6 11 6 1 8 9 1 3 1
5 6 51
2 2 2 5 1
42 61 26 59 100 54
5 10 76
7 5 8 4 7
97 4 44 83 61 45 24 88 44 44
5 8 90
1 1 5 1 3
35 15 53 97 71 83 26 7
5 3 52
1 1 3 1 1
22 6 93
5 6 28
6 6 1 3 1
9 31 2 19 10 27
5 8 31
3 6 2 1 2
32 29 13 7 57 34 9 5
5 6 75
3 3 4 5 4
40 56 38 60 17 3...

output:

0
2
0
0
0
0
0
0
3
4
0
0
0
0
1
1
0
0
0
0
1
1
0
2
2
0
0
0
0
0
2
0
0
0
2
2
0
1
0
0
0
0
1
0
2
4
1
1
0
0
2
0
0
7
0
2
0
0
0
1
1
0
1
0
1
0
0
2
1
0
6
3
0
0
1
0
2
0
0
3
0
1
0
1
0
2
0
0
0
0
1
2
2
4
0
0
0
0
0
0
1
2
2
1
2
2
0
1
1
0
0
0
0
0
1
2
1
4
1
0
4
1
2
1
0
0
0
0
1
2
1
0
0
2
3
1
0
1
1
1
0
1
5
0
1
2
0
2
0
0
...

result:

wrong answer 56th numbers differ - expected: '1', found: '2'