QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #607943 | #5507. Investors | hzy99999 | WA | 2ms | 3608kb | C++20 | 2.2kb | 2024-10-03 17:14:02 | 2024-10-03 17:14:03 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 6010;
int T;
int n, m;
int tr1[N], tr2[N];
int a[N], c[N];
int lowbit(int x)
{
return x & -x;
}
void add(int tr[], int x, int c)
{
for (int i = x; i <= n; i += lowbit(i))
tr[i] += c;
}
int find(int tr[], int x)
{
int res = 0;
for (int i = x; i > 0; i -= lowbit(i))
res += tr[i];
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i], c[i] = 0, tr1[i] = tr2[i] = 0;
int ans = 0;
for (int i = 1; i <= n; i++)
{
int cnt = 0;
for (int j = 1; j < i; j++)
if (a[j] > a[i])
cnt++;
c[i] = cnt;
ans += cnt;
// cout << c[i] << ' ';
}
// cout << endl;
for (int k = 1; k <= m; k++)
{
for (int i = 1; i <= n; i++)
tr1[i] = tr2[i] = 0;
int pos = 0, maxv = 0;
for (int i = n; i; i--)
{
if (!c[i])
continue;
add(tr1, c[i], c[i]);
add(tr2, c[i], 1);
int res1 = find(tr1, c[i] - 1);
int res2 = (find(tr2, n) - find(tr2, c[i] - 1)) * c[i];
if (!pos || maxv < res1 + res2)
pos = i, maxv = res1 + res2;
// cout << ":" << i << ' ' << res1 << ' ' << res2 << ' ' << maxv << endl;
}
if (!maxv)
break;
ans -= maxv;
int t = c[pos];
for (int i = pos; i <= n; i++)
c[i] = max(0, c[i] - t);
}
cout << ans << endl;
}
return 0;
}
/*
4
6 1
4 5 6 2 2 1
6 2
4 5 6 2 2 1
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: 1ms
memory: 3608kb
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: 2ms
memory: 3600kb
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:
0 0 0 58 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 46 3 0 0 1 0 0 0 0 0 0 1 0 3 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 2 0 2 0 0 0 200 0 0 0 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 0 0 0 0 2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 5 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 ...
result:
wrong answer 1st lines differ - expected: '1', found: '0'