QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#785722 | #5417. Chat Program | wlkmok369 | WA | 75ms | 8636kb | C++14 | 1.8kb | 2024-11-26 18:56:43 | 2024-11-26 18:56:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define PII pair<ll, ll>
const ll mod = 1e9 + 7;
const ll MAXN = 500005;
const ll base1 = 131;
const ll base2 = 127;
ll _ = 1, n, m, ans = 0, a[MAXN]; // f[MAXN];
ll c, k, d;
bool check(ll x)
{
vector<ll> f(n + 10, 0);
ll sum = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] >= x)
{
sum++;
}
}
if (sum >= x)
{
return 1;
}
for (int i = 1; i <= n; i++)
{
if (a[i] < x)
{
ll l = max(0ll, i - m + 1);
ll maxn = a[i] + c + d * (i - l);
if (maxn < x)
{
continue;
}
ll minn = a[i] + c;
ll p;
if (d == 0)
{
p = 0;
}
else
{
p = (ll)ceil(1.0 * (x - minn) / (1.0 * d));
}
p = max(p, 0ll);
ll r = i - p;
f[l]++;
f[r + 1]--;
}
}
ll res = 0;
for (int i = 1; i <= n; i++)
{
f[i] += f[i - 1];
res = max(res, f[i]);
}
if (sum + res >= k)
{
return 1;
}
return 0;
}
void solve()
{
cin >> n >> k >> m >> c >> d;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
ll l = 0, r = 1e18;
while (l < r)
{
ll mid = (l + r + 1) >> 1;
if (check(mid))
{
l = mid;
}
else
{
r = mid - 1;
}
}
cout << l << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// cin>>_;
while (_--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3672kb
input:
6 4 3 1 2 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
7 3 2 4 0 1 9 1 9 8 1 0
output:
9
result:
ok 1 number(s): "9"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
8 3 5 0 0 2 0 2 2 1 2 1 8
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 55ms
memory: 8552kb
input:
200000 200000 100000 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 50ms
memory: 7568kb
input:
200000 1 100000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
100001000000000
result:
ok 1 number(s): "100001000000000"
Test #6:
score: 0
Accepted
time: 41ms
memory: 6748kb
input:
200000 1 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
200001000000000
result:
ok 1 number(s): "200001000000000"
Test #7:
score: 0
Accepted
time: 68ms
memory: 7952kb
input:
200000 24420 17993 881138881 700368758 231187558 519018952 260661004 740633836 931672020 155904999 647179942 13217847 779799803 382810661 242588977 708308843 309853544 225488875 389115097 588643904 644409212 704920939 231829287 39891424 881158891 341251089 486868469 808002305 629160633 317239613 771...
output:
964474978
result:
ok 1 number(s): "964474978"
Test #8:
score: 0
Accepted
time: 65ms
memory: 7980kb
input:
200000 31878 34175 753689504 94554240 764252685 385025201 185233994 886343186 532991571 477855721 681289648 908112797 112162074 199451201 408329780 674092805 896613552 521026518 597166827 166901445 503106595 958954753 464273450 431481790 32269637 998211679 557906218 821269178 46577165 394469258 5350...
output:
218913332405
result:
ok 1 number(s): "218913332405"
Test #9:
score: 0
Accepted
time: 66ms
memory: 7784kb
input:
200000 66779 68097 331272836 488739723 665914031 251031451 773370496 810714172 839343832 504839150 83995574 139444234 739491638 942462815 647699510 49942183 188406268 595225798 436622337 155224403 656771269 212988566 991684904 118039448 141911186 286576049 628943968 834536050 463993698 103102683 298...
output:
645490226257
result:
ok 1 number(s): "645490226257"
Test #10:
score: 0
Accepted
time: 65ms
memory: 8548kb
input:
200000 81680 76838 613888876 587957914 198979157 822070409 771572414 956423522 735630675 195386090 413072573 370775671 366821201 759103355 887069240 425791562 480198984 964392370 571045139 69918434 105403235 130585891 929161775 173193325 587989225 533471222 699981718 847802923 586442939 180332329 61...
output:
960936852
result:
ok 1 number(s): "960936852"
Test #11:
score: 0
Accepted
time: 65ms
memory: 8060kb
input:
200000 91220 105205 669606004 726732973 405615679 508461591 318840594 861409998 284631403 936958719 947250328 347040871 121416461 99394333 909156607 370576415 378572464 877013117 152690261 992392798 908066995 281718650 822652735 474896480 407144540 554646021 805052591 301197617 583099837 1953227 277...
output:
10165030223607
result:
ok 1 number(s): "10165030223607"
Test #12:
score: 0
Accepted
time: 75ms
memory: 8636kb
input:
200000 127232 120467 895980455 492723394 67974256 451968973 76401255 93977911 241791237 47804708 449338922 918134740 663986817 479932840 38924404 319676905 350139438 427462753 171072159 971709621 283613979 507344968 142793571 933555229 899830335 24231006 846677144 441919608 211146097 783125953 34819...
output:
915538143
result:
ok 1 number(s): "915538143"
Test #13:
score: 0
Accepted
time: 68ms
memory: 7436kb
input:
200000 143295 141614 955791474 268985895 276555321 556167768 537607093 476166006 132948564 971746533 785402476 871110069 838805339 820188359 777901312 795957142 37915179 710693261 353090372 95835377 270446384 383039611 224736705 6220228 322677117 670856025 250928705 582340637 484301279 806539754 243...
output:
972259005
result:
ok 1 number(s): "972259005"
Test #14:
score: 0
Accepted
time: 65ms
memory: 7896kb
input:
200000 157096 159904 974133295 340215689 706474749 323930074 662376441 153321391 950476963 895688357 752869810 192681616 350060349 824007389 811845511 345866305 725690921 698956476 535108586 146332206 257278790 668799672 380308767 373852519 819152827 612448335 655180267 764230864 757456461 829953554...
output:
957299769272
result:
ok 1 number(s): "957299769272"
Test #15:
score: 0
Accepted
time: 61ms
memory: 8512kb
input:
200000 173159 181051 697507824 116478190 210023105 796725089 123582278 240542194 841634289 819630181 88933363 440624237 156282651 532859126 182226199 527179250 413466662 982186983 717126799 565425255 317740123 618123243 830848122 110081029 241999609 185444425 354399120 536055673 325578934 853367355 ...
output:
920924024876
result:
ok 1 number(s): "920924024876"
Test #16:
score: -100
Wrong Answer
time: 35ms
memory: 7536kb
input:
200000 21000 56984 200 0 412 269 490 216 698 107 517 563 752 856 874 326 317 906 787 1000 686 304 79 362 367 216 923 629 973 921 717 862 73 40 167 932 80 1000 726 719 6 590 989 569 626 228 250 102 723 604 841 104 677 61 207 363 651 864 164 578 41 243 124 531 473 693 178 523 574 113 609 756 178 548 8...
output:
995
result:
wrong answer 1st numbers differ - expected: '953', found: '995'