QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #859266 | #9679. 盒子 | HuTao | 0 | 6ms | 8016kb | C++14 | 2.7kb | 2025-01-17 16:55:40 | 2025-01-17 16:55:40 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
LL c, k, a[N], b[N];
LL f[N];
inline void Solve()
{
scanf("%d%d%lld%lld", &n, &m, &k, &c);
for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]), f[i] = INF;
for(int i = n <= 5000 ? 1 : n - 10; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ ) b[j] = a[j];
LL w = 0, s = 0;
for(int x = i, y = i; x >= 1; )
{
if(y > x) y = x;
if(!b[x])
{
x -- ;
continue;
}
if(s) s -= b[x];
w += b[x] / k * c;
b[x] %= k;
s += b[x];
while(y > max(x - m + 1, 1) && s < k) s += b[ -- y];
// printf("**%d %d %lld %lld\n", x, y, s, w);
// for(int i = 1; i <= x; i ++ ) printf("%lld ", b[i]);
// puts("");
if(s >= k)
{
w += c, s -= k;
LL t = k;
while(t && t >= b[x]) t -= b[x -- ];
b[x] -= t;
}
else
{
// printf("*%d %lld %lld\n", y, f[y - 1] + w + c, w);
x = y - 1, w += c;
}
}
f[i] = min(f[i], w);
// printf("!%d %lld %lld\n", i, f[i], w);
}
for(int i = n <= 5000 ? 1 : n - 10; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ ) b[j] = a[j];
LL w = 0, s = 0;
for(int x = i, y = i; x >= 1; )
{
if(y > x) y = x;
if(!b[x])
{
x -- ;
continue;
}
if(s) s -= b[x];
w += b[x] / k * c;
b[x] %= k;
s += b[x];
while(y > max(x - m + 1, 1) && s < k) s += b[ -- y];
// printf("**%d %d %lld %lld\n", x, y, s, w);
// for(int i = 1; i <= x; i ++ ) printf("%lld ", b[i]);
// puts("");
if(s >= k)
{
w += c, s -= k;
LL t = k;
while(t && t >= b[x]) t -= b[x -- ];
b[x] -= t;
}
else
{
// printf("*%d %lld %lld\n", y, f[y - 1] + w + c, w);
f[i] = min(f[i], f[y - 1] + w + c);
s -= b[x], w += b[x -- ];
}
}
f[i] = min(f[i], w);
// printf("!%d %lld %lld\n", i, f[i], w);
}
printf("%lld\n", f[n]);
}
int main()
{
int T;
scanf("%d", &T);
while(T -- ) Solve();
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 17
Accepted
time: 1ms
memory: 8016kb
input:
3 5 2 4 3 2 2 1 2 2 4 2 4 3 2 4 1 1 10 3 5 1 2 2 2 2 1 1 1 10 2 2
output:
7 7 6
result:
ok 3 number(s): "7 7 6"
Test #2:
score: 0
Wrong Answer
time: 6ms
memory: 8012kb
input:
65 7 1 27 22 70 29 32 15 69 79 84 10 2 2 1 76 63 99 67 75 30 29 45 79 23 9 1 4 3 47 91 10 30 91 29 12 14 53 10 1 5 4 92 22 92 27 30 50 59 6 57 58 5 2 15 15 59 27 70 24 11 5 2 42 42 70 50 42 55 5 6 2 54 46 67 14 52 80 95 3 10 2 89 88 55 14 45 14 90 81 38 40 54 17 5 2 93 86 35 58 76 64 73 6 1 45 43 63...
output:
320 293 287 398 191 222 271 445 285 344 307 270 348 312 370 427 199 184 318 502 344 197 330 233 262 220 454 243 160 280 482 580 330 373 202 293 228 590 268 475 253 494 523 476 186 223 368 323 368 392 507 462 132 209 224 250 297 216 525 557 172 448 433 429 578
result:
wrong answer 52nd numbers differ - expected: '494', found: '462'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #35:
score: 0
Time Limit Exceeded
input:
66664 7 2 82188055 1 35930054 4923258 36288509 46890418 53350617 49812938 68015568 10 2 460335201 1 305598063 240803174 36008172 416771728 391050572 270293987 333994588 436573185 216917970 103343453 9 3 119910901 1 35106715 29444257 72409421 49339248 23617992 3266647 38704192 75874356 72979434 10 1 ...
output:
5 7 4 13 8 3 8 13 3 4 6 10 8 5 11 13 9 14 4 6 4 11 11 4 3 9 6 4 6 5 5 4 4 12 4 9 3 5 10 12 5 5 14 15 4 7 14 14 7 5 7 6 9 5 3 10 8 8 7 6 7 4 11 6 6 5 5 7 4 9 9 9 6 4 4 5 7 6 6 13 6 10 12 5 4 10 14 7 3 7 4 3 6 9 8 13 3 4 8 10 6 6 6 15 10 15 11 3 4 6 7 5 11 13 6 16 13 8 7 10 7 14 11 7 6 9 10 10 8 4 5 7...
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%