QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#77658	#5507. Investors	XKError	WA	74ms	3812kb	C++	2.3kb	2023-02-15 11:46:17	2023-02-15 11:46:19

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-02-15 11:46:19]
评测

测评结果：WA
用时：74ms
内存：3812kb

查看

[2023-02-15 11:46:17]
提交

answer

#include <bits/stdc++.h>

#define maxn 6005

using namespace std;

int n, k;
int a[maxn];
int b[maxn];

int f[maxn];
int g[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);
	}
//	cout<<pl<<" "<<pr<<" "<<vl<<endl;
//	assert(vl >= 0 && pl <= pr);
}

pair<int, int> check(int x) {
	f[n] = 0;
	for (int i = n - 1; i; i--) {
		f[i] = g[i] = 0;
//		f[i] = -1e18;
		for (int j = i + 1; j <= n; j++) {
			moveto(i, j);
			if (f[i] < f[j] + vl - x) {
				f[i] = f[j] + vl - x;
				g[i] = g[j] + 1;
			}
		}
//		cout<<f[i]<<endl;
	}
//	cout<<x<<" "<<f[1]<<" "<<g[1]<<endl;
	return {f[1], g[1]};
}

int main() {
//	freopen("dt.in", "r", stdin);
//	freopen("dt.out", "w", stdout);
	int T;
	scanf("%d", &T);
//	int T = 1;
	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];
		if (k >= n - 1) {
			puts("0");
			continue;
		}
		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;
		pl = pr = n + 1;
		vl = 0;
		int l = 0, r = 1e9, mid;
		while (l < r) {
			mid = (l + r) >> 1;
			if (check(mid).second <= k) r = mid;
			else l = mid + 1;
		}
		auto res = check(l);
//		cout<<l<<" "<<res.first<<" "<<res.second<<endl;
		int ans = res.first + l * res.second;
//		printf("%lld\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
*/

Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3612kb

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: 74ms

memory: 3812kb

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 2nd lines differ - expected: '18', found: '20'