QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #122135 | #149. Peru | tuxiaoxiao | 0 | 9ms | 26372kb | C++14 | 1.1kb | 2023-07-09 15:33:06 | 2023-07-09 15:33:08 |
Judging History
answer
#include<bits/stdc++.h>
#include "peru.h"
#define f(i,x,y) for(int i=x;i<=y;i++)
#define df(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
const ll N=1.1e6,I=1e18,P=1e9+7;
ll n,a[N],x,k,y,z[N],zl,p[N],pl,f[N],fp[N],sz[N],sp[N],fl;
int as;
void rb(ll fg)
{
fl=0;
df(i,zl,1)fp[++fl]=z[i];
f(i,1,pl)fp[++fl]=p[i];
zl=(fl+fg)/2,pl=fl-zl;
df(i,pl,1)p[i]=fp[fl--];
z[1]=p[1]-1;f(i,1,zl)z[i]=fp[fl--];
p[0]=z[1];
f(i,1,pl)sp[i]=min(f[p[i-1]]+a[p[i]],sp[i-1]);
f(i,2,zl)sz[i]=min(f[z[i]]+a[z[i-1]],sz[i-1]);
}
int solve(int N,int K,int *S)
{
n=N,k=K;
f(i,1,n)a[i]=S[i-1];
pl=zl=0;sz[0]=sz[1]=sp[0]=a[0]=I;
// p[++pl]=0;
as=0;
f(i,1,n)
{
if(pl+zl)
{
if(!zl||pl+zl==2)rb(2);
if(z[zl]+k<i)--zl;
}
while(pl+zl)
{
if(!pl)rb(0);
if(a[p[pl]]<=a[i])--pl;//cout<<p[pl],
else break;
}
// df(i,zl,1)cout<<z[i];f(i,1,pl)cout<<p[i];
p[++pl]=i;
sp[pl]=min(f[pl+zl==1?max(i-k,0ll):p[pl-1]]+a[i],sp[pl-1]);
f[i]=min(sz[zl],sp[pl]);//cout<<pl;
if(zl)f[i]=min(f[i-k]+a[z[zl]],f[i]);
else f[i]=min(f[i-k]+a[p[1]],f[i]);
as=(as*23ll+f[i])%P;
}
return as;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 18
Accepted
time: 1ms
memory: 15780kb
input:
2000 170 1054018657 1037445664 1011691297 1009972317 1006506677 1002579733 999792775 999477541 975467893 970302369 968173111 957735623 953086083 938540451 932313113 930563895 924682633 917831575 913506401 908739591 905368525 899452913 894354220 890127447 885923007 583391543 880642788 878397752 87822...
output:
559335223
result:
ok single line: '559335223'
Test #2:
score: 0
Accepted
time: 1ms
memory: 15928kb
input:
2000 100 1019222751 1012312953 1005125581 978875481 967275037 967176717 965763637 960999157 957233281 956958729 953471924 942217905 936256081 925906257 922808341 918616993 918132100 915435367 911342035 909313549 902957201 902119531 900836861 99996937 892982026 884892282 884816596 884102145 883049077...
output:
818524087
result:
ok single line: '818524087'
Test #3:
score: -18
Wrong Answer
time: 0ms
memory: 17932kb
input:
2000 20 1046023457 988320769 85389793 1819030505 635209701 362287065 747208901 958302681 957423952 1241659175 352880697 545051421 356189641 1678485313 76683576 940812217 995748541 1920846205 80556065 1358698601 483048309 1881187901 639822057 873315653 1157374529 225761262 1271878801 421346861 190846...
output:
161956896
result:
wrong answer 1st lines differ - expected: '722220390', found: '161956896'
Subtask #2:
score: 0
Wrong Answer
Test #15:
score: 31
Accepted
time: 9ms
memory: 26372kb
input:
400000 1000 1999989721 1999987224 1999984551 1999977673 1999977545 1999976801 1999975837 1999972607 1999956301 1999952801 1999942489 1999940593 1999940337 1999936353 1999936273 1999926073 1999925513 1999922980 1999918301 1999912501 1999909301 1999906125 1999902913 1999895622 1999893617 1999885490 19...
output:
677928817
result:
ok single line: '677928817'
Test #16:
score: -31
Wrong Answer
time: 9ms
memory: 26092kb
input:
400000 800 1999974677 1999969921 1999965861 1999958493 1999958025 1999951391 1999947061 1999946921 1999944101 1999935101 1999934785 1999933729 1999933327 1999928689 1999921281 224119121 1999917457 1999914027 1999910181 1999903529 1999898241 1999890703 1999885291 1999877461 1999873851 1999865681 1999...
output:
20156574
result:
wrong answer 1st lines differ - expected: '390755425', found: '20156574'
Subtask #3:
score: 0
Runtime Error
Test #34:
score: 0
Runtime Error
input:
2500000 2000 1073315871 1073250349 1072791751 1072104046 1072071097 1071841833 1071809381 1071710686 1071580105 1071482003 1071383725 1071154701 1070499431 1070335288 1070334157 1069943617 1069681476 1069584279 1069581771 1069322519 1069189353 1069125955 1068832186 1068797487 1068662939 1068565681 1...