QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #299180 | #5507. Investors | ushg8877 | WA | 4ms | 9848kb | C++14 | 973b | 2024-01-06 17:32:23 | 2024-01-06 17:32:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=6005;
int f[MAXN][MAXN],s[MAXN][MAXN],a[MAXN];
int n,k;
void solve(){
cin>>n>>k;k++;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n+1;i++) f[0][i]=(i==n+1?0:1e9);
for(int i=1;i<=n+1;i++) for(int j=1;j<=n+1;j++) f[i][j]=1e9,s[i][j]=0;
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) s[i][j]=(a[i]>a[j]);
for(int i=n;i>=1;i--) for(int j=i+1;j<=n;j++) s[i][j]+=s[i+1][j]+s[i][j-1]-s[i+1][j-1];
for(int i=1;i<=k;i++){
auto divid=[&](auto self,int l,int r,int L,int R){
if(l>r) return;
int mid=l+r>>1,bs=0;
for(int j=L;j<=R;j++) if(f[i][mid]>=f[i-1][j+1]+s[mid][j]){
bs=j,f[i][mid]=f[i-1][j+1]+s[mid][j];
}
self(self,l,mid-1,L,bs);self(self,mid+1,r,bs,R);
};
divid(divid,1,n,1,n);
}
cout<<f[k][1]<<endl;
}
int main(){
ios::sync_with_stdio(false);
int _;cin>>_;
while(_--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7612kb
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: 9848kb
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 0 0 0 0 1 0 3 0 0 1 0 0 1 0 0 1 4 0 0 0 0 0 0 0 0 2 0 2 0 0 8 280 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 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 13 1 0 0 0 ...
result:
wrong answer 157th lines differ - expected: '0', found: '1000000000'