QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #35534 | #1191. Reordering the Documents | qingyu_orz | WA | 2ms | 8196kb | C++20 | 1.4kb | 2022-06-16 17:34:52 | 2022-06-16 17:34:55 |
Judging History
answer
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int a[5005];
int qz[5005],hz[5005];
int zd[5005];
int x[5005],y[5005],s[5005];
int f[5005][5005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
int mx1=0,mx2=INT_MAX;
for(int i=1;i<=n;++i){
if(mx1<a[i])qz[i]=1,mx1=a[i];
else qz[i]=0;
}
for(int i=n;i>=1;--i){
if(mx2>a[i])hz[i]=1,mx2=a[i];
else hz[i]=0;
}
for(int i=1;i<=n;++i){
if(!qz[i]&&!hz[i]){
cout<<0<<endl;
return 0;
}
}
int l=0;
for(int i=1;i<=n;++i)if(qz[i])zd[++l]=i;
zd[l+1]=n+1;
int k=0;
int m1=0,h1=0,h2=0;
for(int i=1;i<=l;++i){
if(!h1){
h1=1;
h2=zd[i+1]-zd[i]-1;
m1=a[zd[i]];
}else{
int m2=INT_MAX;
for(int j=zd[i]+1;j<=zd[i+1]-1;++j){
m2=min(m2,a[j]);
}
if(m1>m2){
m1=a[zd[i]];
++h1;
h2+=zd[i+1]-zd[i]-1;
}else{
++k;
x[k]=h1,y[k]=h2;
m1=0,h1=0,h2=0;
h1=1;
h2=zd[i+1]-zd[i]-1;
m1=a[zd[i]];
}
}
}
if(h1){
++k;
x[k]=h1,y[k]=h2;
}
for(int i=1;i<=k;++i)s[i]=s[i-1]+x[i]+y[i];
f[0][0]=1;
for(int i=1;i<=k;++i)for(int j=0;j<=n;++j){
if(j>m||s[i]-j>m)continue;
if(j>=x[i])f[i][j]=(f[i][j]+f[i-1][j-x[i]])%mod;
if(j>=y[i])f[i][j]=(f[i][j]+f[i-1][j-y[i]])%mod;
}
int ans=0;
for(int i=0;i<=n;++i)ans=(ans+f[k][i])%mod;
cout<<ans<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3724kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3808kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #5:
score: 0
Accepted
time: 2ms
memory: 5696kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 8196kb
input:
1000 500 4 5 6 8 10 11 12 13 14 15 20 23 25 26 28 29 33 35 1 2 36 38 3 7 41 9 16 44 48 17 18 51 52 53 19 21 54 22 24 59 61 62 27 67 30 31 32 34 68 69 37 39 73 40 76 77 42 81 83 43 85 45 87 46 89 94 47 95 49 50 97 101 55 103 105 56 57 58 106 60 108 110 63 111 114 64 115 65 119 66 70 71 120 121 72 124...
output:
456993559
result:
wrong answer expected '11363968', found '456993559'