QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #515218 | #5507. Investors | Birdly | WA | 32ms | 13856kb | C++14 | 1.8kb | 2024-08-11 16:08:37 | 2024-08-11 16:08:37 |
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];
void solve(int l1, int r1, int l2, int r2, int kp){
if(l2 > r2) return ;
int mid = (l2+r2) >> 1, pos;
for(int i = l1; i <= mid && i <= r1; i++){
if(f[mid][kp] > f[i][kp-1] + sum[i+1][mid]){
f[mid][kp] = f[i][kp-1] + sum[i+1][mid];
pos = i;
}
}
solve(l1, pos, l2, mid-1, kp);
solve(pos, r1, mid+1, r2, kp);
}
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 i = 1; i <= n; i++)
f[i][1] = sum[1][i];
for(int kp = 2; kp <= k; kp++){
for(int i = 1; i <= n; i++){
solve(1, n, 1, n, kp);
// for(int j = pos[i-1][kp]; j < i; 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: 1ms
memory: 9760kb
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: 32ms
memory: 13856kb
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 4557430888798830399 0 0 1 0 0 0 0 0 0 1 0 4557430888798830399 0 0 1 0 0 1 0 0 1 4 0 0 0 0 0 0 0 0 4557430888798830399 0 2 0 0 8 280 0 0 34 4557430888798830399 0 1 0 0 4557430888798830399 0 0 0 0 0 0 0 4557430888798830399 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 25th lines differ - expected: '3', found: '4557430888798830399'