QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #77636 | #5500. Bars | chenshi# | AC ✓ | 347ms | 5356kb | C++ | 447b | 2023-02-15 10:53:33 | 2023-02-15 10:53:35 |
Judging History
answer
#include<cstdio>
using namespace std;
const int o=5e5+10;
int z,n,p[o],st[o],tp;long long ans;
int main(){
for(scanf("%d",&z);z--;printf("%lld\n",ans),ans=tp=0){
scanf("%d",&n);
for(int i=1;i<=n;st[++tp]=i++)
for(scanf("%d",&p[i]);tp>1&&(st[tp]-st[tp-1])*1ll*(p[i]-p[st[tp]])
>(p[st[tp]]-p[st[tp-1]])*1ll*(i-st[tp]);--tp);
st[0]=1;st[tp+1]=n;
for(int i=1;i<=tp;++i) ans+=p[st[i]]*1ll*(st[i+1]-st[i-1]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
2 4 5 2 2 6 5 1 5 4 4 1
output:
33 29
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 297ms
memory: 3560kb
input:
10000 4 5 2 2 6 5 1 5 4 4 1 197 763787596 15221694 898228999 187472305 466351873 822742732 437754202 800092772 843092246 915675776 166265020 346340615 796714085 497548541 182089610 64356048 363276768 181268733 257949015 236568898 752096761 928725929 443146784 114577469 833053207 38120723 14891030 41...
output:
33 29 382465638565 663641330002 550288673161 458946673513 296420749955 875760099157 632854843886 586309163102 225238173690 716890380495 466644027129 283505446030 585094154153 201707398762 336548832140 483300272586 606382970973 587469399170 408018096564 827347820764 975377092201 925120038848 26408806...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 347ms
memory: 5040kb
input:
6 500000 287001636 204980186 997392401 188445265 873977784 672984447 520446063 460936121 420229946 413937980 95267858 869951831 87353679 843288346 375704325 376217775 66621398 502675506 854835633 99408891 880520553 944446461 690146628 632137514 179514334 551490018 981073461 196185611 719601446 93667...
output:
999978185027008 499999063998982 999946405821678 999970304287364 499999737998030 999979204653771
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 333ms
memory: 3856kb
input:
6 500000 669619127 356830845 494606145 526755381 169647973 602343819 658032437 326960015 207942215 173060393 217232953 314912605 366676785 510103533 489446303 121223259 374781515 484954847 134957195 400053837 122117455 627813351 583524019 624468283 613073257 263488687 242182189 527854337 554306009 1...
output:
953660650057664 883167999492927 499223754839723 667315106896885 904445177106028 879334018232172
result:
ok 6 lines
Test #5:
score: 0
Accepted
time: 341ms
memory: 5356kb
input:
6 500000 12403960 2930024 1808469 4773510 8417429 6369605 2751412 4062450 9895452 9966727 11476617 4854207 2807239 9516332 5730691 731629 2368916 1351133 1435333 6860794 5460899 2506776 7936802 12585522 8631641 3397564 316192 11362360 10913499 5967508 7437490 12648666 5703570 637890 7908197 361480 8...
output:
667267911235251 678790984141243 666630987914525 671493601773996 717382005630376 667971386351316
result:
ok 6 lines