QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94509 | #5832. Make it Smooth | eyiigjkn | 0 | 59ms | 3776kb | C++14 | 1.0kb | 2023-04-06 14:57:49 | 2023-04-06 14:57:51 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
constexpr int V=255,INF=1e9;
int a[110],f[110][310],g[310][10];
inline void chkmin(int &x,const int &y){x=min(x,y);}
int main()
{
int T,D,I,M,n;
cin>>T;
for(int _=1;_<=T;_++)
{
scanf("%d%d%d%d",&D,&I,&M,&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=V;j++) f[i][j]=min(f[i][j]+abs(a[i]-j),f[i-1][j]+D);
if(i>=n) break;
for(int j=M+1;j<=V;j++) chkmin(f[i][j],f[i][j-M]+I);
for(int j=V-M;j;j--) chkmin(f[i][j],f[i][j+M]+I);
for(int j=1;j<=V;j++) fill(g[j],g[j]+__lg(V-j+1)+1,INF);
for(int j=1;j<=V;j++)
{
int le=max(j-M,1),ri=min(j+M,V),k=__lg(ri-le+1);
chkmin(g[le][k],f[i][j]);
chkmin(g[ri-(1<<k)+1][k],f[i][j]);
}
for(int j=1;j<=V;j++)
for(int k=__lg(V-j+1);k;k--)
chkmin(g[j][k-1],g[j][k]),chkmin(g[j+(1<<k-1)][k-1],g[j][k]);
for(int j=1;j<=V;j++) f[i+1][j]=g[j][0];
}
printf("Case #%d: %d\n",_,*min_element(f[n]+1,f[n]+V+1));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 3596kb
input:
100 6 6 2 3 1 7 5 100 1 5 3 1 50 7 0 1 255 3 133 252 183 1 0 1 3 52 227 19 1 0 0 3 1 3 2 1 0 0 3 13 12 13 255 0 0 2 100 200 255 0 0 3 111 220 125 255 0 0 3 0 169 255 255 255 255 3 255 0 255 2 2 254 3 255 0 255 255 255 0 1 13 239 68 38 2 5 102 116 48 24 3 58 34 64 67 92 118 2 199 197 43 19 11 3 22 5 ...
output:
Case #1: 4 Case #2: 17 Case #3: 0 Case #4: 0 Case #5: 2 Case #6: 2 Case #7: 101 Case #8: 135 Case #9: 325 Case #10: 256 Case #11: 3 Case #12: 2 Case #13: 61 Case #14: 61 Case #15: 67 Case #16: 50 Case #17: 62 Case #18: 60 Case #19: 60 Case #20: 218 Case #21: 270 Case #22: 169 Case #23: 115 Case #24:...
result:
wrong answer 6th lines differ - expected: 'Case #6: 1', found: 'Case #6: 2'
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 59ms
memory: 3776kb
input:
100 0 1 255 100 49 143 17 173 79 19 33 114 219 201 224 37 187 158 227 109 190 15 174 108 76 131 3 13 13 11 27 84 74 227 183 188 196 70 173 141 32 151 53 78 83 54 135 86 43 46 242 238 34 152 161 139 61 178 180 42 72 194 222 252 33 70 103 41 51 225 133 36 44 181 52 178 85 240 255 46 184 176 221 227 19...
output:
Case #1: 0 Case #2: 0 Case #3: 0 Case #4: 98 Case #5: 127 Case #6: 118 Case #7: 82 Case #8: 36 Case #9: 67 Case #10: 558 Case #11: 378 Case #12: 552 Case #13: 709 Case #14: 650 Case #15: 675 Case #16: 279 Case #17: 26 Case #18: 4058 Case #19: 6098 Case #20: 50 Case #21: 48 Case #22: 97 Case #23: 96 ...
result:
wrong answer 7th lines differ - expected: 'Case #7: 81', found: 'Case #7: 82'