QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #129304 | #5507. Investors | Forever_Young# | WA | 4ms | 6016kb | C++14 | 1.3kb | 2023-07-22 14:26:58 | 2023-07-22 14:26:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 6066;
int prv[N], nxt[N], a[N], dp[N][N];
int main() {
int t;
scanf("%d", &t);
for(int qq = 1; qq <= t; qq++) {
int n, k;
scanf("%d%d", &n, &k);
fill(prv + 1, prv + 1 + n, 0);
fill(nxt + 1, nxt + 1 + n, 0);
int inv = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
for(int j = 1; j < i; j++) {
if(a[j] > a[i]) {
prv[i]++;
nxt[j]++;
inv ++;
}
}
}
for(int i = 0; i <= n; i++) for(int j = 0; j <= k; j++) {
dp[i][j] = 0;
}
int ans = 0;
for(int i = 1; i <= n; i++) {
int tmp = 0;
for(int j = i; j <= n; j++) {
tmp -= prv[j];
tmp += nxt[j];
for(int l = 0; l < k; l++) {
dp[j][l + 1] = max(dp[j][l + 1], dp[i - 1][l] + tmp);
ans = max(ans, dp[j][l + 1]);
}
}
for(int j = i + 1; j <= n; j++) {
if(a[i] > a[j]) {
prv[a[j]]--;
}
}
}
printf("%d\n", inv - ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
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: 4ms
memory: 6016kb
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:
2 57 101 186 1 64 24 0 76 108 41 0 0 0 1 0 0 25 71 0 0 59 84 190 3 0 0 1 0 1 93 21 54 0 1 1 3 0 0 1 0 1 1 9 32 1 58 55 0 0 0 155 109 37 2 2 0 2 0 0 65 280 0 0 69 4 1 1 0 91 3 0 1 0 88 75 1 1 4 0 0 0 1 0 41 0 0 1 0 0 105 32 88 0 0 60 2 70 98 44 63 0 111 0 75 1 118 22 0 1 2 1 105 5 0 1 0 94 0 0 28 1 0...
result:
wrong answer 1st lines differ - expected: '1', found: '2'