QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#636551 | #6143. 滚榜 | propane | 100 ✓ | 232ms | 330148kb | C++20 | 1.5kb | 2024-10-13 00:29:41 | 2024-10-13 00:29:43 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<map>
#include<algorithm>
using namespace std;
using LL = long long;
LL dp[1 << 13][13][501];
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
pair<int, int> mx{0, 0};
for(int i = 0; i < n; i++){
mx = max(mx, make_pair(a[i], -i));
}
for(int i = 0; i < n; i++){
int need = mx.first - a[i] + (i > -mx.second);
if (need * n <= m){
dp[1 << i][i][need * n] = 1;
}
}
for(int i = 1; i + 1 < 1 << n; i++){
int c = __builtin_popcount(i);
for(int j = 0; j < n; j++){
for(int k = 0; k <= m; k++){
if (dp[i][j][k] == 0) continue;
for(int t = 0; t < n; t++){
if (i >> t & 1) continue;
if (k + (n - c) * max(0, a[j] - a[t] + (j < t)) <= m){
dp[i | (1 << t)][t][k + (n - c) * max(0, a[j] - a[t] + (j < t))] += dp[i][j][k];
}
}
}
}
}
LL ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= m; j++){
ans += dp[(1 << n) - 1][i][j];
}
}
cout << ans << '\n';
}
详细
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 3536kb
input:
2 8 8950 8954
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 5
Accepted
time: 1ms
memory: 3556kb
input:
2 10 8841 8843
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 5
Accepted
time: 0ms
memory: 5648kb
input:
3 9 8765 8761 8765
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 5
Accepted
time: 1ms
memory: 3544kb
input:
3 8 8385 8385 8387
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 5
Accepted
time: 1ms
memory: 3664kb
input:
3 9 8581 8585 8582
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 5
Accepted
time: 0ms
memory: 16192kb
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: 18044kb
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: 16176kb
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: 3ms
memory: 54964kb
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: 7ms
memory: 55376kb
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: 4ms
memory: 56924kb
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: 4ms
memory: 56916kb
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: 53ms
memory: 161836kb
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: 69ms
memory: 169748kb
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: 65ms
memory: 169280kb
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: 57ms
memory: 169268kb
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: 191ms
memory: 315292kb
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: 232ms
memory: 312228kb
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: 191ms
memory: 315060kb
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: 199ms
memory: 330148kb
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