oj.uz

Submission #433190

# Submission time Handle Problem Language Result Execution time Memory
433190 2021-06-19T06:44:43 Z blue Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 374 ms 20808 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
Split the matches into two groups of size N/2.
For each group, create a sorted list of all possible subset sums.
Use two pointers to compute the total number of combinations.
*/

int main()
{
    int N;
    long long M;
    cin >> N >> M;

    int a = N/2, b = N - N/2;

    vector<long long> A(a), B(b);

    for(int i = 0; i < a; i++) cin >> A[i];
    for(int j = 0; j < b; j++) cin >> B[j];

    vector<long long> A_sum, B_sum;
    long long temp;

    for(int mask = 0; mask < (1 << a); mask++)
    {
        temp = 0;
        for(int i = 0; i < a; i++) if(mask & (1 << i)) temp += A[i];
        A_sum.push_back(temp);
    }
    sort(A_sum.begin(), A_sum.end());


    for(int mask = 0; mask < (1 << b); mask++)
    {
        temp = 0;
        for(int i = 0; i < b; i++) if(mask & (1 << i)) temp += B[i];
        B_sum.push_back(temp);
    }
    sort(B_sum.begin(), B_sum.end());

    long long a_index = 0;
    long long b_index = B_sum.size()-1;

    long long res = 0;


    for(a_index = 0; a_index < A_sum.size(); a_index++)
    {
        while(A_sum[a_index] + B_sum[b_index] > M)
        {
            if(b_index == 0) break;
            else b_index--;
        }
        if(A_sum[a_index] + B_sum[b_index] > M) break;
        // cout << a_index << ' ' << b_index << '\n';

        res += b_index + 1;
    }

    cout << res << '\n';
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:51:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(a_index = 0; a_index < A_sum.size(); a_index++)
      |                      ~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1980 KB Output is correct
2 Correct 82 ms 5408 KB Output is correct
3 Correct 374 ms 20788 KB Output is correct
4 Correct 84 ms 5292 KB Output is correct
5 Correct 14 ms 1568 KB Output is correct
6 Correct 9 ms 844 KB Output is correct
7 Correct 19 ms 1476 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2740 KB Output is correct
2 Correct 30 ms 1864 KB Output is correct
3 Correct 145 ms 10512 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 8 ms 916 KB Output is correct
6 Correct 19 ms 1488 KB Output is correct
7 Correct 21 ms 1568 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3500 KB Output is correct
2 Correct 124 ms 6564 KB Output is correct
3 Correct 123 ms 6480 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 84 ms 6556 KB Output is correct
6 Correct 317 ms 20796 KB Output is correct
7 Correct 121 ms 6584 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 12640 KB Output is correct
2 Correct 28 ms 1864 KB Output is correct
3 Correct 10 ms 960 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 7 ms 844 KB Output is correct
6 Correct 253 ms 12716 KB Output is correct
7 Correct 18 ms 1476 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1880 KB Output is correct
2 Correct 82 ms 5328 KB Output is correct
3 Correct 12 ms 960 KB Output is correct
4 Correct 9 ms 844 KB Output is correct
5 Correct 91 ms 6464 KB Output is correct
6 Correct 28 ms 1864 KB Output is correct
7 Correct 330 ms 20808 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 20768 KB Output is correct
2 Correct 30 ms 1980 KB Output is correct
3 Correct 9 ms 928 KB Output is correct
4 Correct 356 ms 20768 KB Output is correct
5 Correct 120 ms 10472 KB Output is correct
6 Correct 19 ms 1476 KB Output is correct
7 Correct 44 ms 2872 KB Output is correct