QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #299156 | #5507. Investors | ushg8877 | WA | 0ms | 9824kb | C++14 | 980b | 2024-01-06 17:27:27 | 2024-01-06 17:27:28 |
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(j>=mid&&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();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7748kb
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: 0ms
memory: 9824kb
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 1000000000 1000000000 145 0 1000000000 1000000000 0 1000000000 1000000000 1000000000 0 0 0 1 0 0 1000000000 1000000000 0 0 1000000000 1000000000 161 3 0 0 1 0 1000000000 1000000000 1000000000 1000000000 0 1 1000000000 3 1000000000 0 1 0 1000000000 1 1000000000 1000000000 1 1000000000 1000000000 0 ...
result:
wrong answer 2nd lines differ - expected: '18', found: '1000000000'