QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#636551#6143. 滚榜propane100 ✓232ms330148kbC++201.5kb2024-10-13 00:29:412024-10-13 00:29:43

Judging History

你现在查看的是最新测评结果

  • [2024-10-13 00:29:43]
  • 评测
  • 测评结果:100
  • 用时:232ms
  • 内存:330148kb
  • [2024-10-13 00:29:41]
  • 提交

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