oj.uz

Submission #241669

# Submission time Handle Problem Language Result Execution time Memory
241669 2020-06-25T08:08:20 Z anonymous Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 681 ms 25156 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#define LL long long
using namespace std;
LL N, M, Wt[45], Ways;
vector <LL> List;
vector <pair<LL,int> > Freq2;
int main() {
    //freopen("bobekin.txt","r",stdin);
    scanf("%lld %lld",&N,&M);
    for (int i=0; i < N; i++) {
        scanf("%lld", &Wt[i]);
    }
    for (int i=0; i < 1<<(N/2); i++) {
        LL wt = 0;
        for (int j=0; j < N/2; j++) {
            if (i & (1<<j)) {wt += Wt[j];}
        }
        if (wt <= M) {
            List.push_back(wt);
        }
    }
    sort(List.begin(), List.end());
    for (int i=0; i<List.size(); i++) {
        if (i + 1 == List.size() || List[i] != List[i+1]) {
            Freq2.push_back({List[i], i+1});
        }
    }

    for (int i=0; i < 1<< (N - N/2); i++) {
        LL wt = 0;
        for (int j=0; j < N - N/2; j++) {
            if (i & (1<<j)) {wt += Wt[j + N/2];}
        }
        if (wt <= M) {
            auto it = upper_bound(Freq2.begin(), Freq2.end(), pair <LL,int> {M - wt + 1, 0});
            Ways += Freq2[it - Freq2.begin() - 1].second;
        }
    }
    printf("%lld",Ways);
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<List.size(); i++) {
                   ~^~~~~~~~~~~~
bobek.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i + 1 == List.size() || List[i] != List[i+1]) {
             ~~~~~~^~~~~~~~~~~~~~
bobek.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~~~~~
bobek.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &Wt[i]);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1348 KB Output is correct
2 Correct 107 ms 6628 KB Output is correct
3 Correct 501 ms 20900 KB Output is correct
4 Correct 110 ms 6676 KB Output is correct
5 Correct 18 ms 1020 KB Output is correct
6 Correct 11 ms 764 KB Output is correct
7 Correct 13 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2284 KB Output is correct
2 Correct 40 ms 2040 KB Output is correct
3 Correct 155 ms 4828 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 20 ms 1564 KB Output is correct
7 Correct 12 ms 256 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 3564 KB Output is correct
2 Correct 164 ms 5508 KB Output is correct
3 Correct 161 ms 5476 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 79 ms 2548 KB Output is correct
6 Correct 247 ms 9328 KB Output is correct
7 Correct 52 ms 256 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 12764 KB Output is correct
2 Correct 37 ms 2040 KB Output is correct
3 Correct 16 ms 1276 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 11 ms 768 KB Output is correct
6 Correct 210 ms 12768 KB Output is correct
7 Correct 12 ms 256 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2040 KB Output is correct
2 Correct 115 ms 6628 KB Output is correct
3 Correct 14 ms 1276 KB Output is correct
4 Correct 15 ms 1276 KB Output is correct
5 Correct 87 ms 2548 KB Output is correct
6 Correct 27 ms 2040 KB Output is correct
7 Correct 134 ms 368 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 25156 KB Output is correct
2 Correct 42 ms 2040 KB Output is correct
3 Correct 16 ms 1276 KB Output is correct
4 Correct 681 ms 25040 KB Output is correct
5 Correct 116 ms 4592 KB Output is correct
6 Correct 21 ms 2040 KB Output is correct
7 Correct 20 ms 288 KB Output is correct