QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#626112#9123. Kth Sumskip2004WA 37ms3652kbC++201.2kb2024-10-09 23:16:322024-10-09 23:16:33

Judging History

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

  • [2024-10-09 23:16:33]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:3652kb
  • [2024-10-09 23:16:32]
  • 提交

answer

#include<bits/stdc++.h>
namespace rgs = std::ranges;
using std::cin, std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
const int N = 50005;
int n, k;
ll a[N], b[N], c[N];
void init(ll * a) {
	for(int i = 1;i <= n;++i) {
		cin >> a[i];
	}
	std::sort(a + 1, a + n);
	a[n + 1] = 1e10;
}
ll solve(ll * a, ll * b, int n, int m, ll v) {
	ll ans = 0;
	for(int i = 0;i < n;++i) {
		ans += std::upper_bound(b, b + m, v - a[i]) - b;
	}
	return ans;
}
ll count(ll * a, ll * b, int n, int m, ll v) {
	int k = 0;
	for(;a[k] + b[k] <= v;++k) ;
	return k * k + solve(a, b + k, k, m - k, v) + solve(b, a + k, k, n - k, v);
}
ll count(ll v) {
	ll sum = 0;
	for(int i = 1;i <= n;++i) {
		sum += count(b + i, c + i, n - i + 1, n - i + 1, v - a[i]);
		sum += count(a + i + 1, c + i, n - i, n - i + 1, v - b[i]);
		sum += count(a + i + 1, b + i + i, n - i, n - i, v - c[i]);
		if(sum > k) return sum;
	}
	return sum;
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k;
	init(a);
	init(b);
	init(c);
	ll l = 0, r = 3e9 + 10;
	for(;l + 1 < r;) {
		ll mid = (l + r) >> 1;
		if(count(mid) >= k) {
			r = mid;
		} else {
			l = mid;
		}
	}
	cout << r << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

2 4
1 2
3 4
5 6

output:

10

result:

ok "10"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3652kb

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: 0
Accepted
time: 0ms
memory: 3612kb

input:

1 1
1000000000
1000000000
1000000000

output:

3000000000

result:

ok "3000000000"

Test #4:

score: -100
Wrong Answer
time: 37ms
memory: 3644kb

input:

314 12491830
429392519 92131736 9460149 448874040 5326166 804308891 571581523 580832602 110825817 11150177 47845585 886171410 888601860 633656718 879205016 333690452 739013504 118317331 8289119 502971381 486014573 167383690 96016893 556946780 634198668 389358242 984894049 735281439 58642904 22106451...

output:

1370242884

result:

wrong answer 1st words differ - expected: '1346801336', found: '1370242884'