ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196954 | #2464. 附魔 | tkswls | 100 | 200ms | 1988kb | C++11 | 1.3kb | 2023-11-04 10:00:43 | 2023-11-04 12:09:31 |
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n, a[305], sum[305], f[305][305], err[305];
const long long inf = 2147483648;
bool cmp(int p, int q) {
return p > q;
}
inline int calc(int p, int q) {
int op = p / q, cnt = 0;
cnt = err[op] * (q - p % q);
cnt += err[op + 1] * (p % q);
if (cnt >= inf) return inf;
// cout << p << " " << q << ' ' << cnt << "[]\n";
return cnt;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1, cmp);
for (int i = n; i >= 1; i--) {
sum[i] = sum[i + 1] + a[i];
}
err[0] = 1;
for (int i = 1; i <= n; i++) {
err[i] = err[i - 1] * 2;
if (err[i] > inf) err[i] = inf + 1;
}
for (int i = 0; i <= n; i++) err[i]--;
f[1][1] = sum[2];
int p, q;
for (int i = 2; i <= n; i++) {
for (int j = i ; j >= 2; j--) {
p = i - j + 1;
f[i][p] = inf;
for (int k = j - 1; k >= 1; k--) {
if (k == 1 && j != 2) break;
q = j - 1 - k + 1;
f[i][p] = min(f[i][p], f[j - 1][q] + calc(p, q) + sum[i + 1]);
}
// cout << i << ' ' << p << "^" << f[i][p] << "\n";
}
}
int ans = inf;
for (int i = 1; i < n; i++) {
ans = min(ans, f[n][i]);
}
if (ans > 2147483647) {
cout << "Too expensive!";
return 0;
}
cout << ans;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1268kb
input:
3 5 2 5
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 10
Accepted
time: 0ms
memory: 1312kb
input:
18 18 43 13 4 43 7 38 20 12 41 33 6 23 23 41 11 21 15
output:
596
result:
ok 1 number(s): "596"
Test #3:
score: 10
Accepted
time: 0ms
memory: 1320kb
input:
20 12 6 37 42 10 6 36 50 17 41 8 40 13 46 20 0 34 16 45 11
output:
711
result:
ok 1 number(s): "711"
Test #4:
score: 10
Accepted
time: 0ms
memory: 1380kb
input:
46 45 47 62 18 59 91 43 33 59 9 21 25 61 12 4 58 3 65 90 65 30 15 92 53 64 62 63 43 68 37 79 63 60 1...
output:
4123
result:
ok 1 number(s): "4123"
Test #5:
score: 10
Accepted
time: 1ms
memory: 1388kb
input:
50 96 8 61 33 39 25 65 26 25 0 32 100 75 80 18 13 4 91 31 5 64 79 68 65 78 39 37 67 34 26 83 27 49 9...
output:
4448
result:
ok 1 number(s): "4448"
Test #6:
score: 10
Accepted
time: 34ms
memory: 1864kb
input:
253 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
252
result:
ok 1 number(s): "252"
Test #7:
score: 10
Accepted
time: 49ms
memory: 1976kb
input:
300 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
299
result:
ok 1 number(s): "299"
Test #8:
score: 10
Accepted
time: 40ms
memory: 1936kb
input:
279 72 7 40 86 86 33 61 23 48 95 80 5 58 13 95 47 34 35 76 62 55 45 36 85 7 48 33 48 53 69 15 29 40 ...
output:
34359
result:
ok 1 number(s): "34359"
Test #9:
score: 10
Accepted
time: 22ms
memory: 1808kb
input:
224 48 17 62 41 26 21 44 82 39 62 48 3 15 33 94 76 88 19 64 2 10 98 18 38 53 95 74 30 83 46 23 43 24...
output:
28384
result:
ok 1 number(s): "28384"
Test #10:
score: 10
Accepted
time: 54ms
memory: 1988kb
input:
300 38 74 14 80 92 86 6 27 29 21 41 52 78 7 17 73 64 4 57 95 32 97 24 96 60 79 37 12 7 61 77 89 98 6...
output:
36952
result:
ok 1 number(s): "36952"
Extra Test:
score: 0
Extra Test Passed