UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168556#30. candyputong10050ms4268kbC++112.7kb2023-02-08 11:26:392023-02-08 11:26:40

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
#define rep(i, a, b) for(int i = a;i <= b; ++ i)
#define per(i, b, a) for(int i = b;i >= a; -- i)
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
namespace fastIO {
	template < typename T > void read (T &x) {x = 0; T flag = 1; char c = getchar (); for ( ; c < '0' || c > '9' ; c = getchar ()) flag = (c == '-') ? -1 : flag; for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c ^ 48); x *= flag;}
	template < typename T, typename ...T1 > void read (T &x, T1 &...x1) {read (x); read (x1...);}
	template < typename T > void write (T x) {if (x < 0) {x = -x; putchar ('-');} if (x / 10) {write (x / 10);} putchar (x % 10 + '0');}
	template < typename T > void writesp (T x) {write (x); putchar (' ');}
	template < typename T > void writeln (T x) {write (x); putchar ('\n');}
}
using namespace fastIO;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
const int N = 100005;
int n, W, a[N], b[N], sa[N], sb[N];
signed main () {
	read (n, W);
	rep (i, 1, n) read (a[i]);
	rep (i, 1, n) read (b[i]);
	sort (a + 1, a + 1 + n);
	reverse (a + 1, a + 1 + n);
	sort (b + 1, b + 1 + n);
	reverse (b + 1, b + 1 + n);	
	rep (i, 1, n) {
		sa[i] = sa[i - 1] + a[i];
		sb[i] = sb[i - 1] + b[i];
	}
	int ans = -1e18;
	rep (i, 1, n) {
		int mn = sa[i], mx, c = 0;
		if (sb[n] < mn) continue;
		int L = 1, R = n;
		while (R - L > 1) {
			int mid = L + R >> 1;
			if (sb[mid] >= mn) R = mid;
			else L = mid;
		}
		if (sb[L] >= mn) mx = sb[L], c += W * L;
		else mx = sb[R], c += W * R;
		c += W * i;
		ans = max (ans, mn - c);
	}
	rep (i, 1, n) {
		int mn = sb[i], mx, c = 0;
		if (sa[n] < mn) continue;
		int L = 1, R = n;
		while (R - L > 1) {
			int mid = L + R >> 1;
			if (sa[mid] >= mn) R = mid;
			else L = mid;
		}
		if (sa[L] >= mn) mx = sa[L], c += W * L;
		else mx = sa[R], c += W * R;
		c += W * i;
		ans = max (ans, mn - c);
	}	
	writeln (ans);
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1148kb

input:

5 895
40 317778 647905 727070 967050
125378 127199 310641 327445 702558

output:

1586956

result:

ok single line: '1586956'

Test #2:

score: 5
Accepted
time: 0ms
memory: 1148kb

input:

5 805
101460 135712 402150 627033 756323
181552 497949 796487 876658 969222

output:

2016238

result:

ok single line: '2016238'

Test #3:

score: 5
Accepted
time: 0ms
memory: 1148kb

input:

5 902
26446 158757 187580 464489 641363
412487 717929 722328 742380 814921

output:

1472321

result:

ok single line: '1472321'

Test #4:

score: 5
Accepted
time: 0ms
memory: 1152kb

input:

10 709
197242 207653 482918 567670 577741 675916 782213 802892 892142 948980
96481 141410 206038 276...

output:

5123274

result:

ok single line: '5123274'

Test #5:

score: 5
Accepted
time: 0ms
memory: 1148kb

input:

10 255
59480 68613 106869 146343 435634 457848 515838 672103 764552 958508
106284 116328 147968 3517...

output:

4181708

result:

ok single line: '4181708'

Test #6:

score: 5
Accepted
time: 0ms
memory: 1152kb

input:

10 760
79084 132937 225186 385029 451968 593802 611467 617268 790575 913213
4379 41170 102616 245438...

output:

3933956

result:

ok single line: '3933956'

Test #7:

score: 5
Accepted
time: 0ms
memory: 1164kb

input:

50 161
16184 31899 99393 104148 109334 110020 136331 144462 159349 162580 187140 190817 211456 25787...

output:

23322981

result:

ok single line: '23322981'

Test #8:

score: 5
Accepted
time: 0ms
memory: 1160kb

input:

50 739
3654 6195 14871 29715 34942 42408 51623 121370 157493 174339 198589 213651 217786 232845 2371...

output:

22579717

result:

ok single line: '22579717'

Test #9:

score: 5
Accepted
time: 0ms
memory: 1160kb

input:

50 167
16828 71020 83704 96393 98947 128874 129838 235787 266649 278412 281265 283308 286629 310439 ...

output:

24663407

result:

ok single line: '24663407'

Test #10:

score: 5
Accepted
time: 0ms
memory: 1164kb

input:

200 51
3108 3942 10420 15738 22686 33278 34200 35334 35496 40409 42163 42828 45876 50227 104418 1111...

output:

95792953

result:

ok single line: '95792953'

Test #11:

score: 5
Accepted
time: 1ms
memory: 1164kb

input:

200 162
2624 5545 8501 10298 10762 12625 14211 19219 24624 26134 42611 43918 48319 57520 61621 67886...

output:

101027383

result:

ok single line: '101027383'

Test #12:

score: 5
Accepted
time: 0ms
memory: 1168kb

input:

200 29
13680 22130 24573 28360 35366 38849 45934 49375 49533 50129 51868 55290 58550 59288 64950 773...

output:

102063645

result:

ok single line: '102063645'

Test #13:

score: 5
Accepted
time: 1ms
memory: 1184kb

input:

1000 722
149 1169 3383 3701 4511 6373 8309 8845 9269 10554 11267 12012 12743 14872 15014 15889 16437...

output:

487382715

result:

ok single line: '487382715'

Test #14:

score: 5
Accepted
time: 0ms
memory: 1188kb

input:

1000 381
1086 2801 3306 4020 4344 4887 7296 8493 8523 9398 10305 10367 11165 11831 12070 14511 16674...

output:

492553372

result:

ok single line: '492553372'

Test #15:

score: 5
Accepted
time: 0ms
memory: 1188kb

input:

1000 697
1161 5433 6294 9273 9666 10586 12335 13027 13037 13059 13125 13210 14464 15935 16576 16724 ...

output:

495812345

result:

ok single line: '495812345'

Test #16:

score: 5
Accepted
time: 0ms
memory: 1316kb

input:

5000 922
683 695 1047 1294 1658 1896 1925 2049 2181 2263 2576 2869 2957 3003 3034 3862 4221 4426 456...

output:

2473532572

result:

ok single line: '2473532572'

Test #17:

score: 5
Accepted
time: 0ms
memory: 1312kb

input:

5000 736
186 222 752 1172 1758 1808 2025 2045 2218 2529 2626 2669 2895 3009 3252 3335 3510 3892 4108...

output:

2502938972

result:

ok single line: '2502938972'

Test #18:

score: 5
Accepted
time: 0ms
memory: 1312kb

input:

5000 825
73 291 394 524 634 891 892 897 1122 1248 1327 2024 2044 2089 2186 2362 2385 2749 2896 3152 ...

output:

2473242177

result:

ok single line: '2473242177'

Test #19:

score: 5
Accepted
time: 28ms
memory: 4268kb

input:

100000 383
21 34 37 38 45 47 58 73 80 85 85 88 89 92 96 98 100 102 115 120 124 133 142 166 190 194 2...

output:

49867278620

result:

ok single line: '49867278620'

Test #20:

score: 5
Accepted
time: 20ms
memory: 4268kb

input:

100000 354
10 19 20 36 37 57 61 69 72 76 77 113 116 119 129 131 152 161 183 185 201 219 223 238 254 ...

output:

49953867041

result:

ok single line: '49953867041'