QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #515197 | #5507. Investors | Birdly | WA | 119ms | 158736kb | C++14 | 1.4kb | 2024-08-11 15:55:47 | 2024-08-11 15:55:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
typedef long long ll;
const int MAXN = 6010;
ll n, a[MAXN], val[MAXN][MAXN], sum[MAXN][MAXN], k, f[MAXN][MAXN], pos[MAXN][MAXN];
int main(){
int t = read();
while(t--){
n = read(), k = read();
k++;
for(int i = 1; i <= n; i++)
for(int kp = 1; kp <= k; kp++)
f[i][kp] = 0x3f3f3f3f3f3f3f3f;
for(int i = 1; i <= n; i++)
a[i] = read(), val[i][i] = 0;
for(int i = 1; i <= n; i++){
for(int j = i-1; j >= 1; j--){
val[j][i] = val[j+1][i] + int(a[j] > a[i]);
// cout << "AAA : " << j << ' ' << i << ' ' << val[j][i] << endl;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
sum[j][i] = sum[j][i-1] + val[j][i];
// cout << "BBB : " << j << ' ' << i << ' ' << sum[j][i] << endl;
}
}
ll ans = 0x3f3f3f3f3f3f3f3f;
for(int kp = 1; kp <= k; kp++){
for(int i = 1; i <= n; i++){
if(kp == 1) f[i][kp] = sum[1][i];
else {
for(int j = pos[i-1][kp]; j < min(pos[i-1][kp] + 100, i*1ll); j++){
if(f[j][kp-1] + sum[j+1][i] < f[i][kp]){
f[i][kp] = f[j][kp-1] + sum[j+1][i];
pos[i][kp] = j;
}
}
}
ans = min(ans, f[n][kp]);
}
}
cout << ans << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11844kb
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: 0
Accepted
time: 0ms
memory: 18052kb
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 0 0 0 0 0 1 0 3 0 0 1 0 0 1 0 0 1 4 0 0 0 0 0 0 0 0 2 0 2 0 0 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 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 13 1 0 0 0 ...
result:
ok 349 lines
Test #3:
score: -100
Wrong Answer
time: 119ms
memory: 158736kb
input:
6 1000 333 84886 84887 84732 83775 83776 83777 81234 80288 79661 79243 79244 78520 78521 78522 78523 78524 78525 79041 79042 78509 78120 77073 77432 77433 76111 75362 75363 75364 75365 75366 73979 73980 73981 73982 73983 73984 73472 73473 73075 72948 72949 72727 72728 72383 72384 72272 72273 72274 7...
output:
0 35910 683 156 31125 242025
result:
wrong answer 2nd lines differ - expected: '15', found: '35910'