QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

你现在查看的是最新测评结果

[2023-09-23 19:35:43]
评测

测评结果：WA
用时：1ms
内存：6104kb

查看

[2023-09-23 19:35:43]
提交

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;
}

源文件, 语言: C++14

詳細信息

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:

result:

wrong answer 30th lines differ - expected: '0', found: '1073741823'