QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94509#5832. Make it Smootheyiigjkn0 59ms3776kbC++141.0kb2023-04-06 14:57:492023-04-06 14:57:51

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-06 14:57:51]
  • 评测
  • 测评结果:0
  • 用时:59ms
  • 内存:3776kb
  • [2023-04-06 14:57:49]
  • 提交

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'