QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #186413 | #5507. Investors | APJifengc | WA | 1ms | 6104kb | C++14 | 1.4kb | 2023-09-23 19:35:43 | 2023-09-23 19:35:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 6005;
int T, n, k;
int a[MAXN];
int f[MAXN][MAXN], c[MAXN][MAXN];
void solve(int l, int r, int L, int R, int k) {
if (l > r) return;
int mid = (l + r) >> 1, M = L;
for (int i = L; i <= R && i < mid; i++) {
if (f[k][mid] > f[k - 1][i] + c[i + 1][mid]) {
f[k][mid] = f[k - 1][i] + c[i + 1][mid];
M = i;
}
}
solve(l, mid - 1, L, M, k), solve(mid + 1, r, M, R, k);
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);
k++;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) c[i][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) if (a[i] > a[j]) c[i][j]++;
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j < n; j++) c[i][j + 1] += c[i][j];
}
for (int i = n; i > 1; i--) {
for (int j = i + 1; j <= n; j++) c[i - 1][j] += c[i][j];
}
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = INT_MAX / 2;
}
}
for (int i = 1; i <= n; i++) f[1][i] = c[1][i];
for (int i = 2; i <= k; i++) solve(1, n, 1, n, i);
printf("%d\n", f[k][n]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5696kb
input:
2 6 1 4 5 6 2 2 1 6 2 4 5 6 2 2 1
output:
2 0
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 6104kb
input:
349 6 2 2 1 2 1 2 1 48 12 42 47 39 39 27 25 22 44 45 13 5 48 38 4 37 6 24 10 42 38 12 37 31 19 44 6 29 17 7 12 7 26 35 24 15 9 37 3 27 21 33 29 34 20 14 30 31 21 48 12 1 43 17 46 17 39 40 22 25 2 22 12 4 11 38 12 4 11 1 5 39 44 37 10 19 20 42 45 2 45 37 20 48 34 16 41 23 18 13 44 47 21 29 4 23 18 16...
output:
1 18 15 145 0 2 1 0 13 13 23 0 0 0 1 0 0 0 0 0 0 0 0 161 3 0 0 1 0 1073741823 0 0 0 0 1 1073741823 3 0 0 1 0 0 1 0 0 1 4 0 0 0 0 0 0 0 0 2 0 2 0 1073741823 8 280 0 0 34 4 0 1 0 0 3 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 2 0 0 0 0 0 0 0 8 1 8 0 0 0 0 1 11 5 0 0 0 6 0 1073741823 0 0 0 1 0 0...
result:
wrong answer 30th lines differ - expected: '0', found: '1073741823'