QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #88200 | #5507. Investors | meaningful# | WA | 7ms | 5496kb | C++14 | 1.1kb | 2023-03-15 15:47:15 | 2023-03-15 15:47:19 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int s[6060][6060],a[6060],g[6060],n,k;
ll f[6060];
int chk(int x)
{
int i,j;
for (i=1;i<=n;i++) f[i]=1e14,g[i]=0;
for (i=1;i<=n;i++) for (j=0;j<i;j++)
{
if (f[j]+s[j+1][i]+x<=f[i]) f[i]=f[j]+s[j+1][i]+x,g[i]=g[j]+1;
}
return g[n]<k;
}
int main()
{
int T;
cin>>T;
while (T--)
{
int i,j;cin>>n>>k;k++;
for (i=1;i<=n;i++) cin>>a[i];
for (i=1;i<=n;i++) for (j=1;j<=n;j++) s[i][j]=0;
for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) if (a[i]>a[j])
{
s[1][j]++;
s[i+1][j]--;
}
for (i=1;i<=n;i++) for (j=1;j<=n;j++) s[i][j]+=s[i-1][j];
for (i=1;i<=n;i++) for (j=1;j<=n;j++) s[i][j]+=s[i][j-1];
int l=0,r=1e9,ans=0;
while (l<=r)
{
int mid=(l+r)>>1;
if (chk(mid)) r=mid-1;
else l=mid+1,ans=mid;
}
int x=ans;
for (i=1;i<=n;i++) f[i]=1e14,g[i]=0;
for (i=1;i<=n;i++) for (j=0;j<i;j++)
{
if (f[j]+s[j+1][i]+x<=f[i]) f[i]=f[j]+s[j+1][i]+x,g[i]=j;
}
ans=0;
int tp=0;
while (n) ans+=s[g[n]+1][n],n=g[n],tp++;
if (tp!=k) ans+=(k-tp)*x;
cout<<ans<<endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3292kb
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: 7ms
memory: 5496kb
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 6 9 145 0 -2 -1 0 1 5 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 4 0 0 0 0 1 7 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 5 1 0 0 0 ...
result:
wrong answer 1st lines differ - expected: '1', found: '-1'