ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#151824 | #30. candy | lzy | 100 | 0ms | 1172kb | C++ | 2.0kb | 2022-07-29 17:00:50 | 2022-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;
}
详细
小提示:点击横条可展开更详细的信息
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'