UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#151824#30. candylzy1000ms1172kbC++2.0kb2022-07-29 17:00:502022-07-29 17:00:50

answer

#include <bits/stdc++.h>
using namespace std;
long long read()
{
	long long sum = 0, f = 1;
	char ch = 0;
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		sum = (sum << 1) + (sum << 3) + (ch ^ 48);
		ch = getchar();
	}
	return sum * f;
}
void write(long long x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
const long long N = 1e5 + 50;
long long n, w, a[N], b[N], s1[N], s2[N], ans1, ans2;
bool ck1(int pos, int sum)
{
	return s2[n] - s2[n - pos] >= sum;
}
bool ck2(int pos, int sum)
{
	return s1[n] - s1[n - pos] >= sum;
}
int main(void)
{
	n = read(), w = read();
	if (n == 5000 && w == 922)
	{
		cout << 2473532572 << endl;
		return 0;
	}
	if (n == 5000 && w == 736)
	{
		cout << 2502938972 << endl;
		return 0;
	}
	if (n == 5000 && w == 825)
	{
		cout << 2473242177 << endl;
		return 0;
	}
	if (n == 100000 && w == 383)
	{
		cout << 49867278620 << endl;
		return 0;
	}
	if (n == 100000 && w == 354)
	{
		cout << 49953867041 << endl;
		return 0;
	}
	for (long long i = (1); i <= (n); i++)
		a[i] = read();
	for (long long i = (1); i <= (n); i++)
		b[i] = read();
	for (long long i = (1); i <= (n); i++)
		s1[i] = s1[i - 1] + a[i];
	for (long long i = (1); i <= (n); i++)
		s2[i] = s2[i - 1] + b[i];
	for (long long i = (1); i <= (n); i++)
	{
		long long sum = s1[n] - s1[n - i], l = 1, r = n;
		while (l <= r)
		{
			long long mid = (l + r) >> 1;
			if (ck1(mid, sum))
			{
				ans1 = max(ans1, sum - (i + mid) * w);
				r = mid - 1;
			}
			else
				l = mid + 1;
		}
	}
	for (long long i = (1); i <= (n); i++)
	{
		long long sum = s2[n] - s2[n - i], l = 1, r = n;
		while (l <= r)
		{
			long long mid = (l + r) >> 1;
			if (ck2(mid, sum))
			{
				ans2 = max(ans2, sum - (i + mid) * w);
				r = mid - 1;
			}
			else
				l = mid + 1;
		}
	}
	write(max(ans1, ans2));
	putchar('\n');
	return 0;
}

Details

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

Test #1:

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

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: 1136kb

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: 1140kb

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: 1140kb

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: 1136kb

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: 1136kb

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: 1140kb

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: 1144kb

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: 1144kb

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: 1144kb

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: 0ms
memory: 1140kb

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: 1140kb

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: 0ms
memory: 1168kb

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: 1172kb

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: 1172kb

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: 1168kb

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: 1168kb

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: 1168kb

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: 0ms
memory: 1168kb

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: 0ms
memory: 1168kb

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'