QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94507#5832. Make it Smootheyiigjkn0 61ms3664kbC++141018b2023-04-06 14:57:092023-04-06 14:57:10

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:10]
  • 评测
  • 测评结果:0
  • 用时:61ms
  • 内存:3664kb
  • [2023-04-06 14:57:09]
  • 提交

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("%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: 0ms
memory: 3652kb

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:

4
17
0
0
2
2
101
135
325
256
3
2
61
61
67
50
62
60
60
218
270
169
115
170
259
231
142
101
22
25
37
71
41
41
103
244
192
192
48
49
60
118
151
36
49
126
96
212
61
61
121
134
203
153
153
37
94
72
72
131
48
49
178
100
100
113
271
79
164
88
144
334
197
172
132
169
48
73
87
85
48
51
28
66
32
54
78
60
54
5...

result:

wrong answer 1st lines differ - expected: 'Case #1: 4', found: '4'

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 61ms
memory: 3664kb

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:

0
0
0
98
127
118
82
36
67
558
378
552
709
650
675
279
26
4058
6098
50
48
97
96
1549
1300
122
2780
3255
117
567
2708
3469
569
4019
251
850
1754
4565
1474
2237
566
1231
359
818
2119
2218
3084
322
3951
5026
457
323
112
2031
1487
446
579
1111
3729
1852
2281
1341
24
2599
2321
1694
219
151
2997
1789
106
4...

result:

wrong answer 1st lines differ - expected: 'Case #1: 0', found: '0'