QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#752774 | #9123. Kth Sum | haiender288 | TL | 0ms | 3732kb | C++23 | 1.5kb | 2024-11-16 09:43:27 | 2024-11-16 09:43:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int uint32_t
#define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
const int maxn = 50004;
int n, k, a[maxn], b[maxn], c[maxn];
int calc(int v) {
int res = 0;
for (int i = 1; i <= n; i++) {
if (a[i] + b[n] + c[n] <= v) {
res += n*n;
} else {
int l = 0;
for (int j = n; j > 0; j--) {
if (a[i] + b[j] + c[n] <= v) {
res += n*j;
break;
} else {
while (l < n && a[i] + b[j] + c[l+1] <= v) l++;
res += l;
}
if (res >= k) return res;
}
}
if (res >= k) return res;
}
return res;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
fileio("");
// freopen("debug.txt", "w", stderr);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
for (int i = 1; i <= n; i++) {
cin >> c[i];
}
sort(a+1, a+1+n);
sort(b+1, b+1+n);
sort(c+1, c+1+n);
int l = 0, r = 3e9;
while (l <= r) {
int mid = (l+r)>>1;
if (calc(mid) >= k) {
r = mid-1;
} else {
l = mid+1;
}
}
cout << l;
return 0 ^ 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
input:
2 4 1 2 3 4 5 6
output:
10
result:
ok "10"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
10 40 11 9 13 12 15 11 11 2 11 17 3 1 10 2 12 18 9 11 11 15 14 9 4 14 16 9 20 2 1 18
output:
14
result:
ok "14"
Test #3:
score: -100
Time Limit Exceeded
input:
1 1 1000000000 1000000000 1000000000