QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #319002 | #8159. 刷野 III | Yuics | 100 ✓ | 9ms | 35416kb | C++20 | 976b | 2024-02-01 14:54:37 | 2024-02-01 14:54:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 2e3 + 7;
constexpr i64 inf = 1e18;
int n, m, top;
int a[N], stc[N];
i64 ans = inf, dp[N][N];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(a + 1, a + n + 1, greater<int>());
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= m; i++) {
stc[top = 1] = i - 1;
for (int j = i; j <= n; j++) {
while (top > 1 && dp[i - 1][stc[top]] - dp[i - 1][stc[top - 1]] >= 1ll * a[j] * (stc[top] - stc[top - 1]))
--top;
dp[i][j] = dp[i - 1][stc[top]] + 1ll * a[j] * (j - stc[top]);
while (top > 1 && (dp[i - 1][j] - dp[i - 1][stc[top - 1]]) * (stc[top] - stc[top - 1]) <= (dp[i - 1][stc[top]] - dp[i - 1][stc[top - 1]]) * (j - stc[top - 1]))
--top;
stc[++top] = j;
}
}
for (int i = 1; i <= n; i++)
ans = min(ans, dp[m][i]);
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 0ms
memory: 35404kb
input:
5 1 2 4 4 4 10000
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 10
Accepted
time: 0ms
memory: 35416kb
input:
2000 234 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 626...
output:
14668306848
result:
ok 1 number(s): "14668306848"
Test #3:
score: 10
Accepted
time: 3ms
memory: 35336kb
input:
2000 345 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 632...
output:
21828817575
result:
ok 1 number(s): "21828817575"
Test #4:
score: 10
Accepted
time: 0ms
memory: 35392kb
input:
500 224 66294782 55099630 8718405 48124447 68016284 2367446 17205043 91335098 87097282 9100752 6491957 48720958 53455828 89125408 25719864 11848122 52244731 69201759 26437312 37777762 82726659 78911899 69681329 16885773 68848203 13447237 57046423 92381205 27704872 43706722 19555119 71696875 62061650...
output:
14853863285
result:
ok 1 number(s): "14853863285"
Test #5:
score: 10
Accepted
time: 0ms
memory: 35268kb
input:
500 10 3 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6...
output:
66
result:
ok 1 number(s): "66"
Test #6:
score: 10
Accepted
time: 3ms
memory: 35396kb
input:
500 10 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4...
output:
44
result:
ok 1 number(s): "44"
Test #7:
score: 10
Accepted
time: 9ms
memory: 35272kb
input:
2000 1843 84604572 4716533 6698574 12319038 50671893 13957944 17671601 11350657 96572857 14254508 17344235 80803829 37343616 11656442 85514739 36882120 79160084 11106020 59949111 94099020 26763090 21776877 72218280 42984613 11032095 62624651 24012793 88044654 23027457 486188 66523748 69020965 681051...
output:
91618811350
result:
ok 1 number(s): "91618811350"
Test #8:
score: 10
Accepted
time: 7ms
memory: 35272kb
input:
2000 1024 70230354 98819891 62478100 10135081 33978136 34810340 16477407 19297418 95495214 20997741 28005411 38336888 84993260 63554536 13453707 51666781 16077717 62825857 43152651 66594616 5742411 14693737 83025479 38612236 54542117 38309252 2507161 7782767 48540912 70109835 81187790 33517835 21329...
output:
67590494017
result:
ok 1 number(s): "67590494017"
Test #9:
score: 10
Accepted
time: 0ms
memory: 35252kb
input:
1483 344 86 20 81 16 69 21 53 99 88 20 1 21 41 12 99 35 93 67 95 11 45 17 96 82 41 41 1 81 1 81 1 47 23 45 33 41 41 76 57 71 50 1 61 22 72 81 5 46 13 73 73 91 97 46 1 70 25 77 85 98 29 71 25 21 96 53 73 95 1 55 99 53 81 57 41 6 5 61 89 88 41 71 1 21 46 88 31 41 69 69 59 1 13 46 77 26 45 61 81 21 559...
output:
3185611
result:
ok 1 number(s): "3185611"
Test #10:
score: 10
Accepted
time: 0ms
memory: 35412kb
input:
1241 19 28 11 93 59 17 11 27 16 55 37 91 41 8 39 5 35 53 90 11 9 79 73 15 41 1 37 13 61 53 71 29 25 92 97 9 9 49 27 9 1 21 65 86 37 30 49 41 21 91 93 88 69 69 45 84 37 7 1 11 12 29 20 98 89 22 72 51 77 59 59 69 29 97 63 3 16 33 80 9 11 57 63 91 93 32 11 22 85 79 91 49 11 81 65 17 53 81 31 27 49 8841...
output:
13574
result:
ok 1 number(s): "13574"