QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #505144 | #6143. 滚榜 | ChenJiarun12345 | 100 ✓ | 860ms | 487864kb | C++14 | 960b | 2024-08-04 20:40:18 | 2024-08-04 20:40:18 |
Judging History
answer
/*
https://www.luogu.com.cn/article/3niqs15y
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define For(i,l,r) for(int i=(l);i<=(r);i++)
#define Rof(i,l,r) for(int i=(l);i>=(r);i--)
constexpr int N=15;
constexpr int M=505;
int n,m,a[N],f[1<<13][N][M];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
For(i,1,n) cin>>a[i];
int mx=0;For(i,1,n) if(a[i]>a[mx]) mx=i;
For(i,1,n) f[(1<<(i-1))][i][n*max(a[mx]-a[i]+(mx<i),0ll)]=1;
For(s,0,(1<<n)-1){
For(i,1,n) if(s&(1<<(i-1))){
For(j,0,m){
For(k,1,n) if(!(s&(1<<(k-1)))){
int t=s|(1<<(k-1)),h=j+max(a[i]-a[k]+(i<k),0ll)*(n-__builtin_popcount(t)+1);
if(h<=m) f[t][k][h]+=f[s][i][j];
}
}
}
}
int ans=0;
For(i,1,n){
For(j,0,m){
ans+=f[(1<<n)-1][i][j];
}
}
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 3564kb
input:
2 8 8950 8954
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 5
Accepted
time: 1ms
memory: 5648kb
input:
2 10 8841 8843
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 5
Accepted
time: 0ms
memory: 3828kb
input:
3 9 8765 8761 8765
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 5
Accepted
time: 1ms
memory: 5608kb
input:
3 8 8385 8385 8387
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 5
Accepted
time: 0ms
memory: 3568kb
input:
3 9 8581 8585 8582
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 5
Accepted
time: 0ms
memory: 20104kb
input:
8 100 8856 8864 8858 8860 8856 8863 8859 8857
output:
17589
result:
ok 1 number(s): "17589"
Test #7:
score: 5
Accepted
time: 0ms
memory: 18072kb
input:
8 100 8238 8239 8245 8244 8245 8244 8238 8244
output:
32475
result:
ok 1 number(s): "32475"
Test #8:
score: 5
Accepted
time: 0ms
memory: 19940kb
input:
8 100 9804 9806 9807 9802 9801 9803 9801 9806
output:
37012
result:
ok 1 number(s): "37012"
Test #9:
score: 5
Accepted
time: 24ms
memory: 63156kb
input:
10 200 8002 8014 8011 8013 8002 8003 8002 8016 8009 8004
output:
606309
result:
ok 1 number(s): "606309"
Test #10:
score: 5
Accepted
time: 24ms
memory: 63420kb
input:
10 200 8324 8323 8328 8322 8325 8328 8328 8323 8334 8323
output:
2504995
result:
ok 1 number(s): "2504995"
Test #11:
score: 5
Accepted
time: 24ms
memory: 63236kb
input:
10 200 9416 9415 9417 9404 9408 9409 9410 9416 9415 9411
output:
2553164
result:
ok 1 number(s): "2553164"
Test #12:
score: 5
Accepted
time: 18ms
memory: 63312kb
input:
10 200 9422 9430 9425 9425 9425 9423 9431 9428 9432 9434
output:
2687280
result:
ok 1 number(s): "2687280"
Test #13:
score: 5
Accepted
time: 217ms
memory: 247560kb
input:
12 300 9281 9292 9279 9280 9289 9291 9285 9279 9280 9281 9290 9281
output:
197821618
result:
ok 1 number(s): "197821618"
Test #14:
score: 5
Accepted
time: 219ms
memory: 245440kb
input:
12 300 9737 9726 9731 9736 9723 9727 9722 9732 9736 9733 9737 9728
output:
196607151
result:
ok 1 number(s): "196607151"
Test #15:
score: 5
Accepted
time: 216ms
memory: 245676kb
input:
12 300 8707 8708 8712 8704 8705 8704 8716 8711 8713 8712 8702 8710
output:
337047589
result:
ok 1 number(s): "337047589"
Test #16:
score: 5
Accepted
time: 213ms
memory: 245576kb
input:
12 300 9200 9194 9191 9195 9197 9192 9206 9206 9197 9198 9192 9202
output:
164570332
result:
ok 1 number(s): "164570332"
Test #17:
score: 5
Accepted
time: 860ms
memory: 487864kb
input:
13 500 8217 8233 8238 8217 8237 8237 8217 8217 8230 8234 8225 8223 8220
output:
1500488819
result:
ok 1 number(s): "1500488819"
Test #18:
score: 5
Accepted
time: 838ms
memory: 487820kb
input:
13 500 9781 9780 9772 9779 9785 9788 9788 9777 9791 9784 9782 9777 9768
output:
4627756434
result:
ok 1 number(s): "4627756434"
Test #19:
score: 5
Accepted
time: 821ms
memory: 487324kb
input:
13 500 8096 8078 8103 8104 8085 8089 8081 8085 8102 8095 8097 8100 8090
output:
1388414345
result:
ok 1 number(s): "1388414345"
Test #20:
score: 5
Accepted
time: 836ms
memory: 487404kb
input:
13 500 8739 8728 8743 8727 8730 8735 8733 8738 8731 8743 8728 8722 8722
output:
3106123719
result:
ok 1 number(s): "3106123719"
Extra Test:
score: 0
Extra Test Passed