QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#514746 | #5507. Investors | qqqaaazzz | WA | 4ms | 5680kb | C++14 | 1.5kb | 2024-08-11 09:35:26 | 2024-08-11 09:35:26 |
Judging History
answer
#include <bits/stdc++.h>
#define FAST ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
int n,k;
int a[6010];
int val[6010][6010];
int f[6010],g[6010];
map<int,int> mp;
int idx;
int t[6010];
const int inf = 1e9;
int lowbit(int x){
return (x&-x);
}
void add(int x,int c){
while(x<=idx){
t[x] += c;
x += lowbit(x);
}
return;
}
int query(int x){
int res = 0;
while(x){
res += t[x];
x -= lowbit(x);
}
return res;
}
void fun(int st){
for (int i=0;i<=idx;i++) t[i] = 0;
for (int i=st;i<=n;i++){
val[st][i] = val[st][i-1]+(query(idx)-query(a[i]));
add(a[i],1);
}
return;
}
void solve(int l,int r,int L,int R){
int mid = (l+r)/2;
int pos = 0;
for (int i=L;i<min(R+1,mid);i++){
if(g[i]+val[i+1][mid]<f[mid]){
f[mid] = g[i]+val[i+1][mid];
pos = i;
}
}
//cout << l << " " << r << " " << pos << "\n";
if(l>=r) return;
solve(l,mid-1,L,pos);
solve(mid+1,r,pos,R);
return;
}
void solve(){
mp.clear();
idx = 0;
cin >> n >> k;
if(n==k){
cout << 0 << "\n";
return;
}
++k;
for (int i=1;i<=n;i++){
cin >> a[i];
mp[a[i]] = 0;
}
for (auto &i : mp) i.second = ++idx;
for (int i=1;i<=n;i++) a[i] = mp[a[i]];
for (int i=1;i<=n;i++) fun(i);
for (int i=1;i<=n;i++) f[i] = inf;
f[0] = 0;
for (int i=1;i<=k;i++){
for (int j=0;j<=n;j++){
g[j] = f[j];
f[j] = inf;
}
solve(0,n,0,n);
}
cout << f[n] << "\n";
return;
}
signed main()
{
int t;
cin >> t;
while(t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5680kb
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: 4ms
memory: 3824kb
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 1 29 25 1000000000 0 0 1000000000 0 0 1 0 0 1 0 0 1 4 0 0 0 0 0 0 0 0 2 0 2 0 0 1000000000 1000000000 0 1000000000 0 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 ...
result:
wrong answer 31st lines differ - expected: '0', found: '1'