QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #77638 | #5507. Investors | XKError | TL | 0ms | 3692kb | C++ | 2.2kb | 2023-02-15 10:58:19 | 2023-02-15 10:58:23 |
Judging History
answer
#include <bits/stdc++.h>
#define maxn 6005
using namespace std;
int n, k;
int a[maxn];
int b[maxn];
int f[maxn][maxn];
int t1[maxn];
int t2[maxn];
void add(int t[], int x, int k) {
for (; x <= n; x += x & -x) t[x] += k;
}
int qry(int t[], int l, int r) {
int res = 0;
for (int x = l - 1; x; x -= x & -x) res -= t[x];
for (int x = r; x; x -= x & -x) res += t[x];
return res;
}
int vl;
int pl, pr;
void moveto(int ql, int qr) {
while (pl > ql) {
--pl;
add(t1, a[pl], 1);
vl += qry(t2, 1, a[pl] - 1);
}
while (pr < qr) {
add(t2, a[pr], -1);
vl -= qry(t1, a[pr] + 1, n);
add(t1, a[pr], 1);
vl += qry(t2, 1, a[pr] - 1);
++pr;
}
while (pl < ql) {
add(t1, a[pl], -1);
vl -= qry(t2, 1, a[pl] - 1);
++pl;
}
while (pr > qr) {
--pr;
add(t1, a[pr], -1);
vl -= qry(t2, 1, a[pr] - 1);
add(t2, a[pr], 1);
vl += qry(t1, a[pr] + 1, n);
}
}
void solve(int d, int l, int r, int L, int R) {
if (r < l) return;
if (L == R) {
for (int i = l; i <= r; i++) moveto(i, L), f[d][i] = f[d - 1][L];
return;
}
// cout<<d<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
int mid = (l + r) >> 1;
int ql = max(L, mid + 1);
int qr = R;
int res = 0, id = 0;
for (int i = ql; i <= qr; i++) {
moveto(mid, i);
if (res < f[d - 1][i] + vl) {
res = f[d - 1][i] + vl;
id = i;
}
}
f[d][mid] = res;
// cout<<mid<<" "<<res<<" "<<id<<endl;
solve(d, l, mid - 1, L, id);
solve(d, mid + 1, r, id, R);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
memset(t1, 0, sizeof t1);
memset(t2, 0, sizeof t2);
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + n + 1);
int tot = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
int ans = 0;
pl = pr = n + 1;
vl = 0;
for (int i = 1; i <= k; i++) {
solve(i, 1, n, 1, n);
ans = max(ans, f[i][1]);
}
// printf("%d\n", ans);
memset(t1, 0, sizeof t1);
for (int i = 1; i <= n; i++) {
ans -= qry(t1, a[i] + 1, n);
add(t1, a[i], 1);
}
printf("%d\n", -ans);
}
return 0;
}
/*
2
6 1
4 5 6 2 2 1
6 2
4 5 6 2 2 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
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
Time Limit Exceeded
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...